143. Reorder 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) {
// devide the list into two half
// corner case will be included
ListNode slow = head;
ListNode fast = head;
while(fast.next!=null && fast.next.next != null){
slow=slow.next;
fast = fast.next.next;
}
// slow will never be null, unless if head is null
// reverse the second part of the list
ListNode first = null;
ListNode second = slow.next;
while(second!=null){
ListNode temp = second.next;
second.next= first;
first = second;
second = temp;
}
// separate the list from the middle
slow.next = null;
ListNode one = head;
ListNode two = first;
while(one!=null && two !=null){
ListNode temp=two.next;
two.next=one.next;
one.next=two;
one = two.next;
two = temp;
}
}
}
Last updated
Was this helpful?