143. Reorder List

143. Reorder List

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

You must do this in-place without altering the nodes’ values.

For example, Given {1,2,3,4}, reorder it to {1,4,2,3}.

思路： 首先将题目所给单链表从中间分割为两个单链表，再将后半个单链表反向，最后合并两个单链表即可。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public void reorderList(ListNode head) { if (head == null || head.next == null) { return; } // find the second half head ListNode fast = head.next; ListNode slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } // reverse the second half ListNode p = slow.next; slow.next = null; // cut the first half ListNode pPre = null; ListNode pSuf = p.next; while (p != null) { pSuf = p.next; p.next = pPre; pPre = p; p = pSuf; } // combine two halves ListNode l1 = head; ListNode l2 = pPre; while (l1 != null && l2 != null) { ListNode l1Next = l1.next; ListNode l2Next = l2.next; l1.next = l2; l2.next = l1Next; l1 = l1Next; l2 = l2Next; } }}

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public void reorderList(ListNode head) { if(head==null) return; // Find the middle node ListNode run = head; ListNode walker = head; while(run!=null && run.next!=null){ run = run.next.next; walker = walker.next; } //Break original list into 2 linkedist ListNode reverse = walker.next; walker.next=null; // Reverse the second linkedList ListNode l1 = head; ListNode prev = null; while(reverse!=null){ ListNode temp = reverse; reverse = reverse.next; temp.next = prev; prev = temp; } ListNode l2 = prev; head = l1; //Merge 2 linkedList while(l2!=null){ ListNode tmpl1 = l1; ListNode templ2 = l2; l1= l1.next; l2 = l2.next; tmpl1.next = templ2; templ2.next=l1; } }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。