143. Reorder List

Description

Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list's nodes, only nodes itself may be changed.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: 1->2->3->4

Output: 1->4->2->3

Example 2

Input: 1->2->3->4->5

Output: 1->5->2->4->3

Solutions

ListNode

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    
    ListNode(int x) {
        val = x;
        next = null;
    }
}

Solution 1

/**
 * Time complexity : O(N)
 * Space complexity : O(N)
 */

class Solution {
    public void reorderList(ListNode head) {
        if(head == null || head.next == null) return;
        
        LinkedList<ListNode> listNodes = new LinkedList();
        while(head != null) {
            ListNode tmp = head;
            head = head.next;
            tmp.next = null;
            listNodes.add(tmp);
        }
        
        head = listNodes.removeFirst();
        ListNode tmp = head;
        while(!listNodes.isEmpty()) {
            tmp.next = listNodes.removeLast();
            
            if(listNodes.isEmpty()) {
                return;
            } else {
                tmp = tmp.next;
            }
            
            tmp.next = listNodes.removeFirst();
            tmp = tmp.next;
        }
    }
}

Solution 2

/**
 * Time complexity : O(N)
 * Space complexity : O(1)
 */

class Solution {
    public void reorderList(ListNode head) {
        if(head == null || head.next == null) return;
        
        // find the middle of linked lis
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // reverse the second part of the list
        ListNode prev = null, curr = slow, tmp;
        while(curr != null) {
            tmp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = tmp;
        }
        
        // merge two sorted linked lists
        ListNode first = head, second = prev;
        while(second.next != null) {
            tmp = first.next;
            first.next = second;
            first = tmp;
            
            tmp = second.next;
            second.next = first;
            second = tmp;
        }
    }
}

Follow up