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.
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 ...
练手的two pointer操作
将linkedlist根据 基偶位置重新排布,不创造额外空间
1 -> 2 -> 3 -> 4 -> 5
p1 = node 1
p2 = node 2
当后面还有剩余的时候我们每次将值写进去一个位置,然后将p向后移动两个
逻辑很简单,但是对于linkedlist一定要熟练
class Solution(object):
def oddEvenList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next:
return head
# now menas at least two elemnt in the array
odd = head
even = head.next
otemp = odd
etemp = even
e1 = True
e2 = True
while e1 or e2:
# print "this is odd"
# print(odd)
#
# print "this is even"
# print(even)
if otemp.next and otemp.next.next:
# if there is the next odd index node
otemp.next = otemp.next.next
otemp = otemp.next
else:
if otemp:
otemp.next = None
e1 = False
if etemp.next and etemp.next.next:
# if there is the next even index node
etemp.next = etemp.next.next
etemp = etemp.next
else:
if etemp:
etemp.next = None
e2 = False
otemp.next =even
print(odd)
return odd
OJ上显示我速度beat 7% only,好奇..说明有更快的算法,估计是有更多的优化,因为我的算法处理even 和odd的重复,肯定有办法将其缩减到一个。。while.. too lazy...