Question brushing record - linked list

Catalog

1. Delete the elements in the linked list

2. Reverse a linked list

2.1 Judge whether the list is palindrome

3. Merge two ordered lists

4. Decomposition of linked list

5. Merge k An ordered list

 7. Find the midpoint of the single linked list

 8. Judge whether the single linked list contains a ring and find out the starting point of the ring

9. Judge whether two single linked lists intersect and find out the intersection

Take a step

---

1. Delete the elements in the linked list

Ordinary node or head node

```java
/**
 * Add virtual node mode
 * Time complexity O(n)
 * Spatial complexity O(1)
 * @param head
 * @param val
 * @return
 */
public ListNode removeElements(ListNode head, int val) {
    if (head == null) {
        return head;
    }
    // Because the deletion may involve the head node , So set dummy node , Unified operation
    ListNode dummy = new ListNode(-1, head);
    ListNode pre = dummy;
    ListNode cur = head;
    while (cur != null) {
        if (cur.val == val) {
            pre.next = cur.next;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return dummy.next;
}
/**
 * Do not add virtual nodes
 * Time complexity O(n)
 * Spatial complexity O(1)
 * @param head
 * @param val
 * @return
 */
public ListNode removeElements(ListNode head, int val) {
    while (head != null && head.val == val) {
        head = head.next;
    }
    // Have been to null, Exit ahead of time
    if (head == null) {
        return head;
    }
    // Determined current head.val != val
    ListNode pre = head;
    ListNode cur = head.next;
    while (cur != null) {
        if (cur.val == val) {
            pre.next = cur.next;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return head;
}
/**
 * Do not add virtual nodes and pre Node The way
 * Time complexity O(n)
 * Spatial complexity O(1)
 * @param head
 * @param val
 * @return
 */
public ListNode removeElements(ListNode head, int val) {
    while(head!=null && head.val==val){
        head = head.next;
    }
    ListNode curr = head;
    while(curr!=null){
        while(curr.next!=null && curr.next.val == val){
            curr.next = curr.next.next;
        }
        curr = curr.next;
    }
    return head;
}

```

2. Reverse a linked list

https://mp.csdn.net/mp_blog/creation/editor/125663957

2.1 Judge whether the list is palindrome

```java
boolean isPalindrome(ListNode head) {
    ListNode slow, fast;
    slow = fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    if (fast != null)
        slow = slow.next;
    
    ListNode left = head;
    ListNode right = reverse(slow);
    while (right != null) {
        if (left.val != right.val)
            return false;
        left = left.next;
        right = right.next;
    }
    
    return true;
}

ListNode reverse(ListNode head) {
    ListNode pre = null, cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

```

3. Merge two ordered lists

Given the linked list of two orders , Make it still orderly after merging

Set the virtual node , Compare the size of the two nodes after the virtual node

```java
ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // Virtual head node
    ListNode dummy = new ListNode(-1), p = dummy;
    ListNode p1 = l1, p2 = l2;
    
    while (p1 != null && p2 != null) {

        // Compare p1 and p2 Two pointers
        // Connect nodes with smaller values to p The pointer
        if (p1.val > p2.val) {
            p.next = p2;
            p2 = p2.next;
        } else {
            p.next = p1;
            p1 = p1.next;
        }
        // p The pointer keeps moving
        p = p.next;
    }
    
    if (p1 != null) {
        p.next = p1;
    }
    
    if (p2 != null) {
        p.next = p2;
    }
    
    return dummy.next;
}
```

4. Decomposition of linked list

Divide the original linked list into two small linked lists , The size of elements in a linked list is smaller than `x`, The elements in another linked list are greater than or equal to `x`, Finally, connect the two linked lists

```java
ListNode partition(ListNode head, int x) {
    // Store less than x Virtual head node of the linked list
    ListNode dummy1 = new ListNode(-1);
    // Store at least x Virtual head node of the linked list
    ListNode dummy2 = new ListNode(-1);
    // p1, p2 The pointer is responsible for generating the linked list of results
    ListNode p1 = dummy1, p2 = dummy2;
    // p Responsible for traversing the original linked list , Similar to the logic of merging two ordered linked lists
    // Here is to decompose a linked list into two linked lists
    ListNode p = head;
    while (p != null) {
        if (p.val >= x) {
            p2.next = p;
            p2 = p2.next;
        } else {
            p1.next = p;
            p1 = p1.next;
        }
        // Disconnect each node in the original linked list next The pointer
        ListNode temp = p.next;
        p.next = null;
        p = temp;
    }
    // Connect two linked lists
    p1.next = dummy2.next;

    return dummy1.next;
}
```

5. Merge k An ordered list

Build the smallest pile , Storage k The head node of a linked list , It can ensure that the current minimum node is obtained every time

```java
ListNode mergeKLists(ListNode[] lists) {
    if (lists.length == 0) return null;
    // Virtual head node
    ListNode dummy = new ListNode(-1);
    ListNode p = dummy;
    // Priority queue , The smallest pile
    PriorityQueue<ListNode> pq = new PriorityQueue<>(
        lists.length, (a, b)->(a.val - b.val));
    // take k The head node of a linked list is added to the minimum heap
    for (ListNode head : lists) {
        if (head != null)
            pq.add(head);
    }

    while (!pq.isEmpty()) {
        // Get the smallest node , Received in the linked list of results
        ListNode node = pq.poll();
        p.next = node;
        if (node.next != null) {
            pq.add(node.next);
        }
        // p The pointer keeps moving
        p = p.next;
    }
    return dummy.next;
}
```

Time complexity O（Nlogk）

## 6. Look for the penultimate of the single linked list k Nodes

Classic double pointer problem

```java
// Returns the penultimate of the linked list k Nodes
ListNode findFromEnd(ListNode head, int k) {
    ListNode p1 = head;
    // p1 Go ahead k Step
    for (int i = 0; i < k; i++) {
        p1 = p1.next;
    }
    ListNode p2 = head;
    // p1 and p2 Go at the same time n - k Step
    while (p1 != null) {
        p2 = p2.next;
        p1 = p1.next;
    }
    // p2 Now point to n - k + 1 Nodes , Countdown k Nodes
    return p2;
}
```

 7. Find the midpoint of the single linked list

This is also a classic topic

```java
ListNode middleNode(ListNode head) {
    // The speed pointer initializes to head
    ListNode slow = head, fast = head;
    // The pointer stops when it comes to the end
    while (fast != null && fast.next != null) {
        // Slow pointer one step , Let's go two steps
        slow = slow.next;
        fast = fast.next.next;
    }
    // The slow pointer points to the midpoint
    return slow;
}
```

 8. Judge whether the single linked list contains a ring and find out the starting point of the ring

Speed pointer ; If there are links in the linked list , The speed pointer will meet

```java
    // The speed pointer initializes to head
    ListNode slow = head, fast = head;
    // The pointer stops when it comes to the end
    while (fast != null && fast.next != null) {
        // Slow pointer one step , Let's go two steps
        slow = slow.next;
        fast = fast.next.next;
        // Fast and slow hands meet , Description contains ring
        if (slow == fast) {
            return true;
        }
    }
    // Does not contain a ring
    return false;
}

ListNode detectCycle(ListNode head) {
    ListNode fast, slow;
    fast = slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) break;

    }
    // The code above is similar to hasCycle function
    if (fast == null || fast.next == null) {
        // fast A null pointer indicates that there is no ring
        return null;
    }

    // Point back to the head node
    slow = head;

    // The speed pointer advances synchronously , The intersection point is the starting point of the ring
    while (slow != fast) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}
```

9. Judge whether two single linked lists intersect and find out the intersection

```java
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    // p1 Point to A Chain header node ,p2 Point to B Chain header node
    ListNode p1 = headA, p2 = headB;
    while (p1 != p2) {
        // p1 Take a step , If you walk to A End of list , go to B Linked list
        if (p1 == null) p1 = headB;
        else            p1 = p1.next;
        // p2 Take a step , If you walk to B End of list , go to A Linked list
        if (p2 == null) p2 = headA;
        else            p2 = p2.next;
    }
    return p1;
}

```

Take a step

```java
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    int lenA = 0, lenB = 0;
    // Calculate the length of two linked lists
    for (ListNode p1 = headA; p1 != null; p1 = p1.next) {
        lenA++;
    }
    for (ListNode p2 = headB; p2 != null; p2 = p2.next) {
        lenB++;
    }
    // Give Way p1 and p2 The same distance to the tail
    ListNode p1 = headA, p2 = headB;
    if (lenA > lenB) {
        for (int i = 0; i < lenA - lenB; i++) {
            p1 = p1.next;
        }
    } else {
        for (int i = 0; i < lenB - lenA; i++) {
            p2 = p2.next;
        }
    }
    // See if the two pointers will be the same ,p1 == p2 There are two situations when ：
    // 1、 Or the two linked lists do not intersect , At the same time, they went to the tail null pointer
    // 2、 Or two linked lists intersect , They came to the intersection of the two linked lists
    while (p1 != p2) {
        p1 = p1.next;
        p2 = p2.next;
    }
    return p1;
}
```