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
YouTube
Examples
Input: 1->2->3->4
Output: 1->4->2->3
Input: 1->2->3->4->5
Output: 1->5->2->4->3
Solutions
// Definition for singly-linked list.
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}/**
* 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;
}
}
}/**
* 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
Last updated
Was this helpful?