Double Pointers

Break loop

See also 141, 142

clip

void dectectAndRemoveLoop(Node node){
    // if list is empty or has only one node
    if (node == null){
        return;
    }

    Node slow = node, fast = node;

    // search for loop
    while (fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;
        if (fast == slow){
            // search connected node and remove the loop
            slow = node;
            while(slow.next != fast.next){
                slow = slow.next;
                fast = fast.next;
            }
            fast.next = null;
            break;
        }
    }
}

287. Find the Duplicate Number

LinkedList Cycle index: 0, 1, 2, 3, 4, 5, 6 value: 2, 6, 4, 1, 3, 1, 5 It value can be index, it will become a cycled linkedlist 0 - > 2 - > 4 -> 3 -> 1 -> 6 -> 5-> [1- >6-> 5 ->1 链表环]

public int findDuplicate(int[] nums) {
    int ptr1 = nums[0];
    int ptr2 = nums[0];

    do{
        ptr1 = nums[ptr1];
        ptr2 = nums[nums[ptr2]];
    }while(ptr1 != ptr2);

    ptr1 = nums[0];

    while(ptr1 != ptr2){
        ptr1 = nums[ptr1];
        ptr2 = nums[ptr2];
    }

    return ptr1;
}

61 Rotate List

Given a linked list, rotate the list to the right by k places, where k is non-negative.

1 create dummy node, a slow and a fast pointer == dummy node 2 get length, fast node move to last 3 slow node move to break index 4 rotate lsit

public ListNode rotateRight(ListNode head, int k) {
    if (head == null || head.next == null){
        return head;
    }

    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode slow = dummy, fast = dummy;

    int i;
    for (i = 0; fast.next != null; i++){  // get length & fast move to last index
        fast = fast.next;
    }

    for (int j = 0; j < i - k%i; j++){    // slow move to break index
        slow = slow.next;
    }

    fast.next = dummy.next;   // rotate list
    dummy.next = slow.next;
    slow.next = null;

    return dummy.next;
}

138 Copy List with random pointer

• HashMap[oldNode, newNode]

• first loop create newNode

• Second loop update next and random pointers

• Space O(n)

 def copyRandomList(self, head: 'Node') -> 'Node':
     if not head:
         return None
     record = {}
     cur = head 
    
     while cur:
         record[cur] = Node(cur.val)
         cur = cur.next
        
     cur = head
     while cur:
         record[cur].next = record[cur.next] if cur.next else None
         record[cur].random = record[cur.random] if cur.random else None
         cur = cur.next
        
     return record[head]

Space O(1) 1 -> 1' -> 2 -> 2' -> 3 -> 3' -> null

1. Copy new nodes after old nodes (including label, next and random)

2. Update random pointers

3. Split the linkedList

def copyRandomList(self, head: 'Node') -> 'Node':
    if not head: return None
    
    # create new node
    cur = head
    while cur:
        node = Node(cur.val)
        node.next = cur.next
        cur.next = node
        cur = cur.next.next
      
    # link new node next and random pointer
    cur = head
    while cur:
        cur.next.random = cur.random.next if cur.random else None
        cur = cur.next.next
    
    # Break new and old nodes
    dummy = new_cur = Node(0)
    cur = head
    
    while cur: # new_cur 在 cur 之前
        new_cur.next = cur.next 
        new_cur = new_cur.next
        
        cur.next = cur.next.next
        cur = cur.next
        
    return dummy.next