1、 Sum two single linked lists

445. Addition of two numbers II
Better understanding of double stack method .

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    // Double stack method 
    LinkedList<ListNode> stack1 = new LinkedList<>();
    LinkedList<ListNode> stack2 = new LinkedList<>();
    ListNode res = null;
    while (l1 != null) {
        stack1.push(l1);
        l1 = l1.next;
    }
    while (l2 != null) {
        stack2.push(l2);
        l2 = l2.next;
    }
    // carry 
    int carry = 0;
    while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
        int sum = 0;
        if (!stack1.isEmpty()) {
            sum += stack1.pop().val;
        }
        if (!stack2.isEmpty()) {
            sum += stack2.pop().val;
        }
        sum += carry;
        // carry 
        carry = sum / 10;
        // And modulus 
        ListNode node = new ListNode(sum % 10);
        node.next = res;
        res = node;
    }
    return res;
}

Construct two stacks from two linked lists , Use the first in, last out feature of the stack , Do two list flashbacks and do calculations , Pay attention to rounding .

2、 Single linked list non recursively flipped , Without the aid of other data structures

206. Reverse a linked list
The flip of single linked list is to flip the pointer of two adjacent nodes . Two extra pointers are needed to store the front and back nodes of the current node .

public static ListNode reverseList(ListNode head) {
    ListNode pre = null;
    while(head!=null){
        ListNode temp = head.next;
        head.next = pre;
        pre = head;
        head = temp;
    }
    return pre;
}

3、 Palindrome list ( use O(n) Time complexity and O(1) Spatial complexity )

234. Palindrome list
Get the middle node position of the linked list through the fast and slow pointer , Reverse the second half of the list , After iteration, the linked list before and after , Whether the judgment value is the same .

public static boolean isPalindrome(ListNode head) {
    // Boundary check , If the list is empty , Or just one node , Go straight back to true
    if (head == null || head.next == null) {
        return true;
    }
    // Use the fast and slow pointer to get the middle node position of the linked list 
    ListNode fast = head;
    ListNode slow = head;
    // When there are even nodes ,fast by null when , Reach the end point 
    // When you have an odd number of nodes ,fast.next by null, Reach the end point 
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    // At the end of the line , Odd number of nodes ,slow Right in the middle , Even number of nodes slow At the beginning of the second half .
    //slow As the starting point of the first half of the linked list ,fast As the starting point of the second half of the linked list 
    fast = slow;
    slow = head;
    // reverse fast The second half of the list at the beginning 
    ListNode pre = null;
    while (fast != null) {
        ListNode temp = fast.next;
        fast.next = pre;
        pre = fast;
        fast = temp;
    }
    // iteration slow And pre, Compare each value 
    while (slow != null && pre != null) {
        if(slow.val!=pre.val){
            return false;
        }
        slow = slow.next;
        pre = pre.next;
    }
    return true;
}

4、 Circular list

141. Circular list
Check whether there are rings in the linked list , There are two ways ： Use HashSet Or speed pointer .

public static boolean hasCycle(ListNode head) {
    // Boundary check , If the linked list is empty or has only one node , Go straight back to false
    if (head == null || head.next == null) {
        return false;
    }
    // Use the speed pointer 
    ListNode fast = head.next;
    ListNode slow = head;
    // The fast and slow pointers don't coincide and they loop all the time 
    while (fast != slow) {
        // As long as the fast pointer reaches the end of the list , Then there is no ring 
        if (fast == null || fast.next == null) {
            return false;
        }
        fast = fast.next.next;
        slow = slow.next;
    }
    return true;
}

5、 Delete all the values in the linked list as val The node of

203. Remove linked list elements
A sentinel node is used to remove the linked list , Simplify the deletion of .

public static ListNode removeElements(ListNode head, int val) {
    // Use sentinel nodes 
    ListNode sentinel = new ListNode(0);
    sentinel.next = head;
    ListNode pre = sentinel;
    while (head != null) {
        // If the current node is the node to be deleted 
        if (head.val == val) {
            // The previous node points directly to the next node 
            pre.next = head.next;
        } else {
            //pre Move backward 
            pre = head;
        }
        head = head.next;
    }
    return sentinel.next;
}

6、 Merge two ordered lists

21. Merge two ordered lists
Need to use sentinel node .

public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // Defining sentinel nodes 
    ListNode head = new ListNode(0);
    ListNode pre = head;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            pre.next = l1;
            l1 = l1.next;
        } else {
            pre.next = l2;
            l2 = l2.next;
        }
        pre = pre.next;
    }
    if (l1 == null) {
        pre.next = l2;
    } else {
        pre.next = l1;
    }
    return head.next;
}

summary

The commonly used algorithm of linked list often uses the fast and slow pointer and sentry node . Just use the sentinel node head There will be pre The nodes match .