Subject to introduce

Force buckle 143: leetcode-cn.com/problems/re…

Solution one: storage

The disadvantage of linked lists is that they can’t be stored randomly, so when we want to fetch the last element, we have to go through them from the beginning, which is time-consuming. The second time I take the last element, I have to go through it again.

So a simple and crude idea is to store a linked list in a linear list, and then use a double pointer to fetch elements from the beginning to the end.

The code is 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 void reorderList(ListNode head) {
        if(head == null && head.next == null) {
            return;
        }

        List<ListNode> nodeList = new ArrayList<>();
        ListNode temp = head;    
        while(temp ! =null) {
            nodeList.add(temp);
            temp = temp.next;
        }

        int left = 0;/ / pointer to the left
        int right = nodeList.size() - 1;/ / right pointer
        while(left < right) {
            ListNode leftNode = nodeList.get(left);
            ListNode rightNode = nodeList.get(right);
            if(leftNode.next == rightNode) {
                // If the number of nodes is even, set the next pointer on the middle right node to null to prevent the linked list from forming a loop
                rightNode.next = null;
            }else {
                rightNode.next = leftNode.next;
                leftNode.next = rightNode;
            }
            left++;
            right--;
        }

        if(left == right) {
            ListNode leftNode = nodeList.get(left);
            // If the number of nodes is odd, set the next pointer of the intermediate node to null to prevent the linked list from forming a loop
            leftNode.next = null; }}}Copy the code

Complexity analysis

• Time complexity: O(N), where N is the number of nodes in the linked list.
• Spatial complexity: O(N), where N is the number of nodes in the linked list. Mainly the overhead of linear tables.

Method 2: Find list midpoint + list reverse + merge list

Note that the target list is the result of merging the left half of the original list with the reversed right half.

So our task can be divided into three steps:

• Find the midpoint of the original list. We can use the fast and slow Pointers to find the middle nodes of the list O(N).

• Reverse the right half of the original list. We can use the iterative method to reverse the list.

• Merge both ends of the original linked list.

The code is as follows:

// find the midpoint + reverse the last half + merge the first and second parts
public void reorderList(ListNode head) {
    if(head==null || head.next==null || head.next.next==null) {
        return;
    }
    
    // 1. Find the midpoint and make slow point to the midpoint, or left midpoint
    ListNode slow = head, fast = head.next;
    while(fast! =null&& fast.next ! =null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // 2. Break the midpoint and reverse the bottom half
    ListNode head2 = null, next = slow.next;
    slow.next = null;
    slow = next;
    while(slow ! =null) {
        next = slow.next;
        slow.next = head2;
        head2 = slow;
        slow = next;
    }

    // 3. Merge linked list head and head2
    ListNode curr = head;
    ListNode curr2 = head2;
    while(curr ! =null&& curr2 ! =null) { next = curr.next; curr.next = curr2; curr2 = curr2.next; curr.next.next = next; curr = next; }}Copy the code

Complexity analysis

• Time complexity: O(N), where N is the number of nodes in the linked list.
• Space complexity: O(1).