143. Reorder List

  • 24.9%

https://leetcode.com/problems/reorder-list/#/description

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.

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

方法一:

按照题意,先找一半处,后一半反转,然后并入前一段。

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void reorderList(ListNode* head) {
if(!head || !head->next)
return;
ListNode* fast = head, * slow = head;
while(fast->next!=NULL && fast->next->next!=NULL){
fast = fast->next->next;
slow = slow->next;
}
fast = slow->next;
ListNode* pre = NULL;
while(fast){
ListNode* nex = fast->next;
fast->next = pre;
pre = fast;
fast = nex;
}
fast = pre;
slow->next = NULL;
slow = head;
while(fast!=NULL){
ListNode* nex = fast->next;
fast->next = slow->next;
slow->next = fast;
slow = slow->next->next;
fast = nex;
}
return;
}
};

49ms, September 22, 2016

https://discuss.leetcode.com/topic/7425/a-concise-o-n-time-o-1-in-place-solution

A concise O(n) time, O(1) in place solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// O(N) time, O(1) space in total
void reorderList(ListNode *head) {
if (!head || !head->next) return;

// find the middle node: O(n)
ListNode *p1 = head, *p2 = head->next;
while (p2 && p2->next) {
p1 = p1->next;
p2 = p2->next->next;
}

// cut from the middle and reverse the second half: O(n)
ListNode *head2 = p1->next;
p1->next = NULL;

p2 = head2->next;
head2->next = NULL;
while (p2) {
p1 = p2->next;
p2->next = head2;
head2 = p2;
p2 = p1;
}

// merge two lists: O(n)
for (p1 = head, p2 = head2; p1; ) {
auto t = p1->next;
p1 = p1->next = p2;
p2 = t;
}

//for (p1 = head, p2 = head2; p2; ) {
// auto t = p1->next;
// p1->next = p2;
// p2 = p2->next;
// p1 = p1->next->next = t;
//}
}

https://discuss.leetcode.com/topic/4061/my-o-n-c-method-accepted

My O(n) C++ Method, accepted

Firstly, I split the list from the middle into two lists. One from head to middle, and the other from middle to the end. Then we reverse the second list. Finally we merge these two lists. O(n) time complexity and O(1) space complexity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void reorderList(ListNode *head) {
if(head == NULL || head->next == NULL || head->next->next==NULL)
return;
//find the middle of the list, and split into two lists.
ListNode *p=head,*q=head;
while(p && q && q->next && q->next->next){
p=p->next;
q=q->next->next;
}

ListNode *mid = p->next;
p->next=NULL;
p=head;
//reverse from the middle to the end
ListNode *q1=mid, *q2,*q3;
if(mid->next){
q1=mid;
q2=mid->next;
while(q2){
q3=q2->next;
q2->next=q1;
q1=q2;
q2=q3;

}
mid->next=NULL;
}
q=q1;
//merge these two list
ListNode *s=p;
p=p->next;
while(p && q){
s->next=q;
s=s->next;
q=q->next;

s->next=p;
s=s->next;
p=p->next;
}
if(p){
s->next=p;
}
if(q){
s->next=q;
}
}
};

https://discuss.leetcode.com/topic/10894/share-a-consise-recursive-solution-in-c

Share a consise recursive solution in C++

The recursive idea have been posted by yucheng.wang. Given a example, 1->2->3->4->5, the solution will reorder node(3), then reorder 2 and 4 to have (2->4->3), then 1 and 5 get have 1->5->2->4->3. Each call of reorderList(ListNode* head, int len) will return the last element after this reorderList() call.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int getLength(ListNode *head){
int len = 0;
while( head != NULL ){
++len; head = head->next;
}
return len;
}

ListNode * reorderList(ListNode *head, int len){
if(len == 0)
return NULL;
if( len == 1 )
return head;
if( len == 2 )
return head->next;
ListNode * tail = reorderList(head->next, len-2);
ListNode * tmp = tail->next;
tail->next = tail->next->next;
tmp->next = head->next;
head->next = tmp;
return tail;
}

void reorderList(ListNode *head) { //recursive
ListNode * tail = NULL;
tail = reorderList(head, getLength(head));
}

https://discuss.leetcode.com/topic/3345/a-python-solution-o-n-time-o-1-space

A python solution O(n) time, O(1) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
# Splits in place a list in two halves, the first half is >= in size than the second.
# @return A tuple containing the heads of the two halves
def _splitList(head):
fast = head
slow = head
while fast and fast.next:
slow = slow.next
fast = fast.next
fast = fast.next

middle = slow.next
slow.next = None

return head, middle

# Reverses in place a list.
# @return Returns the head of the new reversed list
def _reverseList(head):

last = None
currentNode = head

while currentNode:
nextNode = currentNode.next
currentNode.next = last
last = currentNode
currentNode = nextNode

return last

# Merges in place two lists
# @return The newly merged list.
def _mergeLists(a, b):

tail = a
head = a

a = a.next
while b:
tail.next = b
tail = tail.next
b = b.next
if a:
a, b = b, a

return head


class Solution:

# @param head, a ListNode
# @return nothing
def reorderList(self, head):

if not head or not head.next:
return

a, b = _splitList(head)
b = _reverseList(b)
head = _mergeLists(a, b)

https://discuss.leetcode.com/topic/13869/java-solution-with-3-steps

Java solution with 3 steps

This question is a combination of Reverse a linked list I & II. It should be pretty straight forward to do it in 3 steps :)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public void reorderList(ListNode head) {
if(head==null||head.next==null) return;

//Find the middle of the list
ListNode p1=head;
ListNode p2=head;
while(p2.next!=null&&p2.next.next!=null){
p1=p1.next;
p2=p2.next.next;
}

//Reverse the half after middle 1->2->3->4->5->6 to 1->2->3->6->5->4
ListNode preMiddle=p1;
ListNode preCurrent=p1.next;
while(preCurrent.next!=null){
ListNode current=preCurrent.next;
preCurrent.next=current.next;
current.next=preMiddle.next;
preMiddle.next=current;
}

//Start reorder one by one 1->2->3->6->5->4 to 1->6->2->5->3->4
p1=head;
p2=preMiddle.next;
while(p1!=preMiddle){
preMiddle.next=p2.next;
p2.next=p1.next;
p1.next=p2;
p1=p2.next;
p2=preMiddle.next;
}
}

https://discuss.leetcode.com/topic/18092/java-solution-with-3-steps

Java solution with 3 steps

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public class Solution {

public void reorderList(ListNode head) {
if (head == null || head.next == null)
return;

// step 1. cut the list to two halves
// prev will be the tail of 1st half
// slow will be the head of 2nd half
ListNode prev = null, slow = head, fast = head, l1 = head;

while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}

prev.next = null;

// step 2. reverse the 2nd half
ListNode l2 = reverse(slow);

// step 3. merge the two halves
merge(l1, l2);
}

ListNode reverse(ListNode head) {
ListNode prev = null, curr = head, next = null;

while (curr != null) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}

return prev;
}

void merge(ListNode l1, ListNode l2) {
while (l1 != null) {
ListNode n1 = l1.next, n2 = l2.next;
l1.next = l2;

if (n1 == null)
break;

l2.next = n1;
l1 = n1;
l2 = n2;
}
}

}
谢谢你,可爱的朋友。