首页 > 代码库 > [Leetcode] Reorder List

[Leetcode] Reorder List

2024-08-02 10:55:11   218人阅读

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


联系
我们