Skip to main content

linked-list

Linked list#

temp, head, prev, next, ptr, node, tempNode, position, slowPtr, fastPtr

  • temp = temp.next;

  • head to the start of linked list

  • while(temp.next!==null) ; while(temp!==null)

  • Traverse linked list using two pointers. Move one pointer by one and the other pointers by two. When the fast pointer reaches the end slow pointer will reach the middle of the linked list.

  • First, move the reference pointer to n nodes from head. Now move both pointers one by one until the reference pointer reaches the end. Now the main pointer will point to nth node from the end.

  • to detect a loop, move one pointer doubly fast than the other, they will meet

  • sometimes we have to copy the data into the node. example - Given only a pointer to a node to be deleted in a singly linked list, how do you delete it? we dont have head pointer in this case.

  • find intersection - get both the lists length by traversiong, get the difference, then move pointer by the difference in the long list then move equally

  • to find the cycle length, find once the slow and fast pointer meet, then move any one pointer one step until they meet again, thats the cycle length

  • to find the cycle start point, find the lenth of cycle , then use 2 pointers with an initial separation by cycle length and move step by step

  • We can use the detect cycle using slow and fast in normal problems as well like (Happy number problem) ~find the missdle of the LL, then reverse the second half

  • Doing a deep copy of linked list with random an next pointer - Use Map https://www.geeksforgeeks.org/clone-linked-list-next-arbit-pointer-set-2/