143. Reorder List
Last updated
Last updated
// 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;
}
}
}