# Double Pointers

## Break loop

See also 141, 142

[clip](https://www.youtube.com/watch?time_continue=202\&v=_BG9rjkAXj8)

```java
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 链表环]

```java
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

```java
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)

```python
 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&#x20;

1\. Copy new nodes after old nodes (including label, next and random)&#x20;

2\. Update random pointers&#x20;

3\. Split the linkedList

```python
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
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://netjimmy.gitbook.io/code-interview-note/linkedlist/double_pointers.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.