2022.02.13 - NC001. Reverse linked list

1. subject

2. Ideas

(1) Utilization stack （ Overtime ）

• First use the stack push() Press the nodes into the stack in turn , Reuse stack pop() Pop up the nodes in turn , Reversal can be achieved , But it will time out .

(2) Discussion by situation

• Discuss separately 0 Nodes 、1 Nodes 、2 Nodes 、3 More than nodes ：0 Nodes 、1 Nodes return directly head that will do ;2 Just reverse the nodes directly ;3 More than nodes need to use two variables to point to head Of next and next Of next,head Used to point to the node pointed to in the reverse operation ,next Used to point to the node pointed to in the reverse operation , That is, the head node of the new linked list ,nextNext Used to point to the head node of the original linked list .

(3) Optimize

• And (2) The idea is basically the same , But more concise .
• Variable last Point to the node pointed to in the reverse operation , Variable cur Point to the node pointed to in the reverse operation , That is, the head node of the new linked list , Variable next Point to the head node of the original linked list .
• Because the order in the loop body is moving variables next -> Reverse operation -> Moving variables last -> Moving variables cur, So finally, variables last Point to the head node of the new list .

3. Code

import java.util.Stack;

public class Test {
    
    public static void main(String[] args) {
    
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        Solution2 solution = new Solution2();
        ListNode listNode = solution.ReverseList(listNode1);
        System.out.println(listNode.val);
        System.out.println(listNode.next.val);
        System.out.println(listNode.next.next.val);
    }
}

class ListNode {
    
    int val;
    ListNode next = null;

    ListNode(int val) {
    
        this.val = val;
    }
}

class Solution {
    
    public ListNode ReverseList(ListNode head) {
    
        Stack<ListNode> stack = new Stack<>();
        while (head != null) {
    
            stack.push(head);
            head = head.next;
        }
        head = stack.pop();
        ListNode listNode = head;
        while (!stack.isEmpty()) {
    
            listNode.next = stack.pop();
            listNode = listNode.next;
        }
        return head;
    }
}

class Solution1 {
    
    public ListNode ReverseList(ListNode head) {
    
        if (head != null) {
    
            // At least two points 
            if (head.next != null) {
    
                // At least three points 
                if (head.next.next != null) {
    
                    ListNode next = head.next;
                    ListNode nextNext = next.next;
                    head.next = null;
                    while (nextNext != null) {
    
                        next.next = head;
                        head = next;
                        next = nextNext;
                        nextNext = next.next;
                    }
                    next.next = head;
                    head = next;
                }
                // There are only two points 
                else {
    
                    head.next.next = head;
                    head = head.next;
                    head.next.next = null;
                }
            }
        }
        return head;
    }
}

class Solution2 {
    
    public ListNode ReverseList(ListNode head) {
    
        if (head == null) {
    
            return null;
        }
        ListNode last = null;
        ListNode cur = head;
        ListNode next = null;
        while (cur != null) {
    
            next = cur.next;
            cur.next = last;
            last = cur;
            cur = next;
        }
        return last;
    }
}