Leetcode question brushing 07 double pointer

Double pointer

Basic knowledge of

1. Introduce

Double pointers are an idea or a technique , Not a particularly specific algorithm .

Specifically, two variables are used to dynamically store two nodes , It's convenient for us to do some operation . Usually used in linear data structures .

Especially the problem of linked list , It is often necessary to use two or more pointers to remember the nodes on the linked list , Do something .

2. classification

Common double pointer mode ：

• Same speed pointer ： Two pointers on the linked list , One starts first , The other set off behind and followed at the same speed .
  • Find the inverse of the linked list ： Make the double pointer move forward synchronously through the temporary pointer
  • Find the penultimate of the list k Elements ： Let the first pointer go forward k Step , Then the two pointers move forward at the same speed , The first pointer goes to the end , Then the following pointer is the penultimate k Elements
• Speed pointer ： Two pointers on the linked list start from the same node , One pointer advances faster than the other （ such as , Twice as much as the other pointer ）
  • Calculate the midpoint of the linked list ： The speed pointer starts from the node , The fast pointer moves two nodes forward , The full pointer moves one node forward , Finally, when the fast pointer reaches the end , The full pointer points to the middle node .
  • Determine if the list has links ： The speed pointer starts from the node , If there are rings in the list , The two pointers will eventually meet in the ring
  • Find the length of the link in the linked list ： As long as a pointer doesn't move after meeting , The other pointer advances until it meets the calculated length .

title

Reverse a linked list

1. Title Description

Topic link

2. Analysis idea and code

• iteration ： Using two Pointers cur and prev, The initial conditions cur Point to head,prev Point to null, Then promise cur.next = prev, Both pointers move to the right at the same time and continue the operation until cur Just want to empty , This is the time prev The node pointed to is head
• recursive ： Divide big problems into small ones , Reverse the entire linked list , First assume that the latter part of the linked list has been reversed , Therefore, you only need to modify the current node next The next one of the points to the current node , Current node next Point to null, Return to the new node , The detailed ideas are as follows .

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
class Solution {
    
    public ListNode reverseList(ListNode head) {
    
        if (head == null || head.next == null)  return head;
        ListNode prev = null;
        ListNode cur = head;
        
        while (cur != null) {
    
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        
        return prev;
    }
    
    // recursive
    public ListNode reverseList(ListNode head) {
    
        if (head == null || head.next == null)  return head;
        
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        cur = head
        prev = None
        while cur:
            next = cur.next
            cur.next = prev
            prev = cur
            cur = next
        return prev
    
    # recursive
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        newHead = self.reverseList(head.next)
        
        head.next.next = head
        head.next = None
        return newHead

Delete the last of the linked list N Nodes

1. Title Description

Topic link

2. Solution ideas and code

Double pointer ： Let the two pointers point to head And empty nodes （ The next node of an empty node is head）, Then point to head Go n Step , Then point to head And the two pointers of the null node go down at the same time until they point to head Is empty , At this time, the second pointer points to the penultimate n The previous node of a node , Then delete the next node .

	public ListNode removeNthFromEnd(ListNode head, int n) {
    
        ListNode head1 = new ListNode();
        head1.next = head;
        ListNode fast = head;
        ListNode slow = head1;
        while (n > 0) {
    
            fast = fast.next;
            n -- ;
        }
        
        while (fast != null) {
    
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return head1.next;
    }

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        head1 = ListNode(0, head)
        slow = head1
        fast = head
        
        while n > 0:
            fast = fast.next
            n -= 1
        
        while fast:
            fast = fast.next
            slow = slow.next
            
        slow.next = slow.next.next
        
        return head1.next

Sort list

1. Title Description

Topic link

2. Solution ideas and code

• Use a hash table to map the number of occurrences of each number , Then find the element that only appears once
• Get the number on each digit of the answer , Because all the other numbers appear three times , So each digit of the answer is equal to the result and modulus of all digits 3, Note that if the target language does not distinguish between signed and unsigned numbers , The highest position requires special judgment .

	public ListNode sortList(ListNode head) {
    
        return sortList(head, null);
    }
    
    public ListNode sortList(ListNode head, ListNode tail) {
    
        if (head == null) {
    
            return head;
        }
        
        if (head.next == tail) {
    
            head.next = null;
            return head;
        }
        
        ListNode slow = head, fast = head;
        
        while (fast != tail) {
    
            slow = slow.next;
            fast = fast.next;
            if (fast != tail)   fast = fast.next;
        }
        
        ListNode mid = slow;
        ListNode list1 = sortList(head, mid);
        ListNode list2 = sortList(mid, tail);
        return merge(list1, list2);
    }
    
    public ListNode merge(ListNode head1, ListNode head2) {
    
        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead, cur1 = head1, cur2 = head2;
        
        while (cur1 != null && cur2 != null) {
    
            if (cur1.val > cur2.val) {
    
                cur.next = cur2;
                cur2 = cur2.next;
            } else {
    
                cur.next = cur1;
                cur1 = cur1.next;
            }
            cur = cur.next;
        }
        
        cur.next = (cur1 == null ? cur2 : cur1);
        return dummyHead.next;
    }

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def sortFunc(head: ListNode, tail: ListNode) -> ListNode:
            if not head:
                return head
            if head.next == tail:
                head.next = None
                return head
            slow = fast = head
            while fast != tail:
                slow = slow.next
                fast = fast.next
                if fast != tail:
                    fast = fast.next
            mid = slow
            return merge(sortFunc(head, mid), sortFunc(mid, tail))
            
        def merge(head1: ListNode, head2: ListNode) -> ListNode:
            dummy = ListNode(0)
            cur, cur1, cur2 = dummy, head1, head2
            while cur1 and cur2:
                if cur1.val <= cur2.val:
                    cur.next = cur1
                    cur1 = cur1.next
                else:
                    cur.next = cur2
                    cur2 = cur2.next
                cur = cur.next
            cur.next = cur2 if not cur1 else cur1
            return dummy.next
        
        return sortFunc(head, None)

Delete duplicate elements from the sort list

1. Title Description

Topic link

2. Solution ideas and code

If the next node value of the current node is equal to the current node , Skip the next node .

	public ListNode deleteDuplicates(ListNode head) {
    
        if (head == null)   return head;
        
        ListNode cur = head;
        
        while (cur.next != null) {
    
            if (cur.next.val == cur.val) {
    
                cur.next = cur.next.next;
            } else {
    
                cur = cur.next;
            }
        }
        return head;
    }

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head:
            return head
        
        cur = head
        
        while cur.next:
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return head

Circular list

1. Title Description

Topic link

2. Solution ideas and code

• Hashtable ： A ring will surely meet , Save the node to the hash table , If there is no ring, it must be traversed
• Speed pointer ： Quick pointer to head The next node of , Slow pointer to head, Then the fast pointer takes two steps at a time , Slow pointer one step at a time , If there are rings, they will meet , otherwise fast The pointer must point to null , Return at this time false

	public boolean hasCycle(ListNode head) {
    
        if (head == null || head.next == null)  return false;
        
        ListNode slow = head;
        ListNode fast = head.next;
        
        while (slow != fast) {
    
            if (fast == null || fast.next == null)  return false;
            fast = fast.next.next;
            slow = slow.next;
        }
        return true;
    }

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            return False
        
        slow = head
        fast = head.next
        
        while fast != slow:
            if not fast or not fast.next:
                return False
            fast = fast.next.next
            slow = slow.next
        return True