328. Odd Even Linked List

  • 42.5%

https://leetcode.com/problems/odd-even-linked-list/#/description

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

1
2
3
Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.

Note:

The relative order inside both the even and odd groups should remain as it was in the input.

The first node is considered odd, the second node even and so on …


方法一:

两个指针,分别指向奇偶序列的头部

再两个指针,分别随着链表向后走

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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
if(head == NULL || head->next == NULL)
return head;
ListNode *p1, *p2, *h2;
p1 = head;
p2 = p1->next;
h2 = p2;
while(p2!=NULL && p2->next != NULL){
p1->next = p2->next;
p2->next = p2->next->next;
p1 = p1->next;
p2 = p2->next;
}
p1->next = h2;
return head;
}
};

我的代码实现:

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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
if(!head || !head->next)
return head;
ListNode* even = new ListNode(-1);
ListNode* odd = new ListNode(-1);
ListNode* cur = head, *p1 = even, *p2 = odd;
while(cur){
p1->next = cur;
p2->next = cur->next;
p1 = p1->next;
p2 = p2->next;
if(!cur->next || !cur->next->next)
break;
cur = cur->next->next;
}
p1->next = odd->next;
return even->next;
}
};

方法二:

https://discuss.leetcode.com/topic/34837/simple-c-solution-o-n-time-o-1-space

Simple C++ solution, O(n) time, O(1) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ListNode* oddEvenList(ListNode* head) 
{
if(!head) return head;
ListNode *odd=head, *evenhead=head->next, *even = evenhead;
while(even && even->next)
{
odd->next = odd->next->next;
even->next = even->next->next;
odd = odd->next;
even = even->next;
}
odd->next = evenhead;
return head;
}

https://discuss.leetcode.com/topic/34473/my-c-solution

My c++ solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {

if(head == NULL || head->next == NULL)
return head;
ListNode *odd = head;
ListNode *even_head = head->next;
ListNode *even = even_head;

while(even != NULL && even->next != NULL)
{
odd->next = even->next;
odd = odd->next;
even->next = odd->next;
even = even->next;
}
odd->next = even_head;
return head;
}
};

https://discuss.leetcode.com/topic/34309/clear-python-solution

Clear Python Solution

1
2
3
4
5
6
7
8
9
10
11
def oddEvenList(self, head):
dummy1 = odd = ListNode(0)
dummy2 = even = ListNode(0)
while head:
odd.next = head
even.next = head.next
odd = odd.next
even = even.next
head = head.next.next if even else None
odd.next = dummy2.next
return dummy1.next

https://discuss.leetcode.com/topic/36552/python-solution-with-two-pointers-o-n

Python solution with two pointers O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution(object):
def oddEvenList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head:
return head
odd=head
even=head.next
while even and even.next!=None:
temp = even.next
even.next = even.next.next
temp.next = odd.next
odd.next = temp
odd=odd.next
even=even.next
return head

read in two node at a time:

first node(odd) goes into odd.next

2nd node(even).next = next even node (node.next.next)

rinse and repeat

so basically

1 - 2 - 3 - 4- 5- 6 -7-null

odd = 1 even = 2

temp = 3

even(2).next = even.next.next(4)

temp(3).next=odd(1).next(2)

(this makes sure the end of odd always points to start of even)

odd(1).next = temp(3)

odd = odd.next(3) move the pointer

even = even.next(4) move the pointer

1-3(odd)-2-4(even)-5-null

1-3-5(odd)-2-4-null(even)

1-3-5-7(odd)-2-4-6-null(even)


解题思路

head作为头部,每次只作为头部索引,然后引导odd和even,最后拼接,return

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution(object):
def oddEvenList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
dummy1 = odd = ListNode(0)
dummy2 = even = ListNode(0)
while head:
odd.next = head
even.next = head.next
odd = odd.next
even = even.next
head = even.next if even else None
odd.next = dummy2.next
return dummy1.next

java

https://discuss.leetcode.com/topic/34280/straigntforward-java-solution-o-1-space-o-n-time

1
2
3
4
5
6
7
8
9
10
11
12
public ListNode oddEvenList(ListNode head) {
if(head==null||head.next==null) return head;
ListNode odd=head,ehead=head.next,even=ehead;
while(even!=null&&even.next!=null){
odd.next=even.next;
odd=odd.next;
even.next=odd.next;
even=even.next;
}
odd.next=ehead;
return head;
}

谢谢你,可爱的朋友。