TwoPointers

concept

TwoPointers refer to TwoPointers that are fast and slow to advance a linked list, which I divide into two categories.

  • Type 1: The starting point is different. Fast goes before slownstep
  • Type 2: different step sizes. Fast advances faster than slow, for examplefast = fast->next->next; slow = slow->next, fastStep lengthfor2And the missileStep lengthfor1
  • And of course, there’s another alternative that I also classify as TwoPointers, and I’ll show you an interesting example

What problems can TwoPointers solve?

  1. Find the midpoint of the list
  2. Find the NTH node from the bottom of the list
  3. Identify and detect linked list Cycle problems
  4. Find the intersection of two lists

876.Middle of the Linked List

Given a non-empty, singly linked list with head node head, return a middle node of linked list. If there are two middle nodes, return the second middle node.

Example 1:

Input: [1,2,3,4,5] Output: Node 3 from this list (Serialization: [3,4,5]) The returned node has value 3. (The judge’s serialization of this node is [3,4,5]). Note that we returned a ListNode object ans, such that: ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

Example 2:

Input: [1,2,3,4,5,6] Output: Node 4 from this list (Serialization: [4,5,6]) Since the list has two middle nodes with values 3 and 4, we return the second one.

If we know the length of the linked list, the problem will be easy. Do we need to go through a loop to figure out the length? TwoPointers can tell you that you don’t have to, you know, do a loop.

void middleList(struct ListNode* head, struct ListNode** mid){
	struct ListNode *fast = head, *slow = head;
	while(fast && fast->next){
		fast = fast->next->next;
		slow = slow->next;
	}
	*mid = slow;
}
Copy the code

The correctness is obvious.

19. Remove Nth Node From End of List

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5.

Similarly, we don’t need to know the length of the list in advance, we let the fast pointer take n steps first, and then fast and slow go hand in hand, so slow and fast are always n apart, and when FAST gets to the tail, slow and the tail are n apart, and that’s it.

Code:

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    if(! head)return NULL;
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    struct ListNode* tmp = NULL;
    while(n--)
        fast = fast->next;
    if(! fast){ tmp = head; head = head->next;free(tmp);
        return head;
    }
    while(fast->next){
        fast = fast->next;
        slow = slow->next;
    }
    tmp = slow->next;
    slow->next = slow->next->next;
    free(tmp);
    return head;
}
Copy the code

Again, it makes a judgment on the deletion of the head node.

142. Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Set the speed pointer to head, so that fast has 1 more steps than slow, so that if there is a loop, slow will already be in the loop when it enters the loop, and by the time they meet for the first time, FAST will have gone n more laps than slow. At this point, let slow point to head again, and walk at the same step size as fast. When they meet again, they enter the loop.

Distance between entry position and head: LENGTH of a ring: R Distance between first encounter and head: s Distance between first encounter and entry position: x

The following relationship exists: S = 2s + NR

a + x = s = nr

The last formula tells slow to start at the beginning. Fast starts from its current position with a step size of 1, and starts at the same time. Slow takes a step, so fast has actually taken a + x + A step. But since a + x = nr, in fact, the fast position coincides with the slow position, and the slow position also happens to be where the loop enters. The correctness of the algorithm is verified.

Code:

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while(fast ! =NULL&& fast->next ! =NULL){
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow){
            slow = head;
            while(fast && slow ! = fast){ fast = fast->next; slow = slow->next; }returnslow; }}return NULL;
}
Copy the code

160. Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

B: B1 → B2 → B3 → C1 → c2 → c3

begin to intersect at node c1.

This is the use of alternative fast and slow Pointers, and you should find out how they change direction. It is proved that the time complexity of this algorithm is O(m+ N).

Code:

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if(headA == NULL || headB == NULL)
        return NULL;
   struct ListNode *pa = headA, *pb = headB;
    while(true) {if(pa == pb)
			return pa;
		if(pa->next == NULL&& pb->next ! =NULL){
			pa = headB;
			pb = pb->next;
			continue;
		}
		if(pa->next ! =NULL && pb->next == NULL){
			pb = headA;
			pa = pa->next;
			continue;
		}
		if(pa->next == NULL && pb->next == NULL)
			return NULL;
		pa = pa->next;
		pb = pb->next;		
	}
	return NULL;     
}
Copy the code

In fact, the existence of PA and Pb seems to connect two linked lists together. If there is an intersection point, they must meet, because in fact, they advance the same linked list, which is the virtual linked list with length M + N. It’s just alternating speed, and in the worst case, they meet after m+ N advances.

byebye~