首页 > 代码库 > [Leetcode] Reorder List
[Leetcode] 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}.
基本思路：
目前想到的解法是，分三步来做：
1. 找出中间节点
2. 把中间节点之后的后半部分链表反序
3. 把前半部分链表及后半部分链表合并
Solution 1:
自己的代码，写得太乱了。。。很多地方可以改进的。。。
1 /** 2 * Definition for singly-linked list. 3 * class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { 7 * val = x; 8 * next = null; 9 * }10 * }11 */12 public class Solution {13 public void reorderList(ListNode head) {14 if(head==null||head.next==null)15 return;16 ListNode fast=head;17 ListNode slow=head;18 while(fast.next!=null&&fast.next.next!=null){19 fast=fast.next.next;20 slow=slow.next;21 }22 ListNode head2=slow.next;23 slow.next=null;24 head2=reverseList(head2);25 while(head!=null&&head2!=null){26 ListNode temp=head.next;27 head.next=head2;28 ListNode temp2=head2.next;29 head2.next=temp;30 head=temp;31 head2=temp2; 32 } 33 }34 35 private ListNode reverseList(ListNode head) {36 37 if(head==null||head.next==null)38 return head;39 // TODO Auto-generated method stub40 ListNode dummy=new ListNode(-1);41 dummy.next=head;42 ListNode pre,l1,l2,l3;43 pre=dummy;44 l1=pre.next;45 ListNode last=l1;46 l2=l1.next;47 l3=l2.next;48 while(l3!=null){49 l2.next=l1;50 l1=l2;51 l2=l3;52 l3=l3.next;53 }54 dummy.next=l2;55 l2.next=l1;56 last.next=null;57 return dummy.next;58 }59 }
Solution 2:
大神的代码：
1 public class ReorderList { 2 public void reorderList(ListNode head) { 3 if (head == null || head.next == null) 4 return; 5 ListNode fast = head; 6 ListNode late = head; 7 while (fast.next != null && fast.next.next != null) { 8 fast = fast.next.next; 9 late = late.next;10 }11 ListNode ret = new ListNode(0);12 ListNode cur = ret;13 ListNode leftHalf = head;14 ListNode rightHalf;15 if (fast.next != null) {16 rightHalf = reverseList(late.next);17 late.next = null;18 } else {19 rightHalf = reverseList(late);20 ListNode tmp = head;21 while (tmp.next != late) {22 tmp = tmp.next;23 }24 tmp.next = null;25 }26 leftHalf = head;27 while (leftHalf != null && rightHalf != null) {28 cur.next = leftHalf;29 leftHalf = leftHalf.next;30 cur = cur.next;31 cur.next = rightHalf;32 rightHalf = rightHalf.next;33 cur = cur.next;34 }35 if (leftHalf != null) {36 cur.next = leftHalf;37 } else if (rightHalf != null) {38 cur.next = rightHalf;39 }40 head = ret.next;41 }42 43 private ListNode reverseList(ListNode head) {44 ListNode cur = head;45 ListNode prev = null;46 ListNode next = null;47 while (cur != null) {48 next = cur.next;49 cur.next = prev;50 prev = cur;51 cur = next;52 }53 return prev;54 }55 }
[Leetcode] Reorder List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。