preface

Reverse the list of related questions, in the interview showed a high frequency, so summarize the next few list of related questions

  1. NC78 Reverse Linked List (simple)
  2. NC21 Interval inversion specified in the linked list (medium)
  3. Nodes in the NC50 list are flipped in groups of k (medium)

1. Reverse the list

Description: input a list, reverse the list, output the new list header.

Thinking analysis:

  • The iterative implementation uses a pre-node pre and current node cur to loop through the updates
  • Recursive implementations define recursive functions, handle base cases, and call recursive functions on the next node of the current node

AC code:

Iterative version: time complexity O(n) space complexity O(1)

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    
    ListNode pre = null;
    ListNode next;

    while(head ! =null) {
        next = head.next;
        head.next = pre;
        pre = head;
        head = next;
    }
    return pre;
}
Copy the code

Recursive version: time complexity O(n) space complexity O(n)

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    
    ListNode res = reverseList(head.next);
    head.next.next = head;
    head.next = null;

    return res;
}
Copy the code

2. Reverse the specified interval in the linked list

Description: You are given the head pointer of a singly linked list with two integers left and right, where left <= right. Invert the list node from position left to position right and return the inverted list.

First, go through the list to find the start node in the left position and the tail node in the right + 1 position, modify the termination condition in the list I, record the leftPreNode in the left, and finally connect them together

Tip: Linked list related problems usually add a virtual head node;

In the following implementation code, the code to find the specified location node and the code to reverse the specified interval node are put into a separate method. In fact, the last walk can complete the problem, and the logic is extracted for readability

AC code:

public ListNode reverseBetween(ListNode head, int left, int right) {
    ListNode dumpNode = new ListNode(-1);
    dumpNode.next = head;

    ListNode leftPreNode = findNode(dumpNode, left);
    ListNode leftNode = leftPreNode.next;
    ListNode rightNextNode = findNode(dumpNode, right + 2);

    leftPreNode.next = reverse(leftNode, rightNextNode);
    leftNode.next = rightNextNode;

    return dumpNode.next;
}

ListNode findNode(ListNode head, int index) {
    int count = 1;
    while(count ! = index) { head = head.next; count++; }return head;
}

ListNode reverse(ListNode head, ListNode tail) {
    if (head == tail || head.next == tail) return head;
    
    ListNode pre = null;
    ListNode next;
    while(head ! = tail) { next = head.next; head.next = pre; pre = head; head = next; }return pre;
}
Copy the code

3. Nodes in the linked list are flipped every k in a group

Description: the nodes in the given list are flipped every k in a group, and the flipped list is returned; If the number of nodes in the list is not a multiple of K, the last remaining nodes are left as is; You cannot change the value in a node, only the node itself.

Input: head = [1,2,3,4,5], k = 3Copy the code

Use the reverse(ListNode head, ListNode tail) function in the linked list to assist. The recursive function reverseKGroup is defined to return the head node after inversion. After reversing an interval, the tail node in the interval points to the head node in the next interval

AC code:

    public ListNode reverseKGroup (ListNode head, int k) {
        ListNode cur = head;
        int count = 0;
        while(cur ! =null) {
            cur = cur.next;
            count++;
            if (count == k) {
                break; }}if(count ! = k) {return head;
        }

        ListNode ans = reverse(head, cur);
        head.next = reverseKGroup(cur, k);
        return ans;
    }
Copy the code