Description
You are given the head of a singly linked-list. The list can be represented as:
L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be on the following form:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
You may not modify the values in the list’s nodes. Only nodes themselves may be changed.
Example 1:
Input: head = [1,2,3,4]
Output: [1,4,2,3]
Example 2:
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
Constraints:
- The number of nodes in the list is in the range
[1, 5 * 10^4]. 1 <= Node.val <= 1000
Approach - Reverse and Merge
- Split list into two parts and reverse the second half then rearrange the pointers
- Split will be such as for 1 2 3 4 5 it would split to 1 2 3 and 4 5 this can be achieved by starting slow with head and fast with head next
- In the last loop standard stuff I wrote in reverse order one as well so first save the next pointers then starts readjusting and then move forward using the saved pointers
Time:O(n) Space:O(1)- At most you are iterating the entire List
/**
* 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) {
ListNode slow = head;
ListNode fast = head.next;
//slow would not reach null obv
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode prev = null;
ListNode curr = slow.next;
slow.next = null; //to make sure the new list end is null
//reverse order standard code
while (curr != null) {
ListNode tmp = curr.next;
curr.next = prev;
prev = curr;
curr = tmp;
}
ListNode curr1 = head;
ListNode curr2 = prev;
//looping second half is enough
while (curr2 != null) {
ListNode tmp1 = curr1.next;
ListNode tmp2 = curr2.next;
curr1.next = curr2;
curr2.next = tmp1;
curr1 = tmp1;
curr2 = tmp2;
}
}
}