Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给一个单链表,要求重新排序,前一半为链表的奇数位,后一半为偶数位,e.g.,
Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]

设置三个指针位置,odd表示当前奇数位处理到哪里,r表示目前已处理到的位置的下一位,even表示当前偶数位处理到哪里,另设置pos记录当前已经处理过多少个(用于判断奇偶)
1.如果当前处理偶数位,odd指向r,r指向next,even不变,e.g.,
1->3->2->4->5->6->7 (此时odd指向3,even指向2,r指向4)
在处理节点4时,指针更新为:odd依旧指向3,even指向4,r指向5,链表顺序不变

2.如果当前处理奇数位,先用临时变量记录第一个偶数位(first_even = odd.next),r的下一位(r_next = r.next),然后分五步改变链表指针顺序
1->3->2->4->5->6->7 (此时odd指向3,even指向4,r指向5)
s1:更新odd.next = r (让3的下一位指向5)
s2:更新r.next = first_even (让5的下一位指向2)
s3:更新even.next = r_next (让4的下一位指向6)
s4:更新odd = r (此时odd指向5)
s5:更新r = r_next (此时r指向6)
更新后链表顺序为:1->3->5->2->4->6->7 (此时odd指向5,even指向4,r指向6)

复杂度O(n),内存O(1)

 1 #328
 2 #Runtime: 73 ms
 3 #Memory: 17.1 MB
 4 
 5 # Definition for singly-linked list.
 6 # class ListNode(object):
 7 #     def __init__(self, val=0, next=None):
 8 #         self.val = val
 9 #         self.next = next
10 class Solution(object):
11     def oddEvenList(self, head):
12         """
13         :type head: ListNode
14         :rtype: ListNode
15         """
16         if not head:
17             return head
18         pos = 1
19         r = head.next
20         odd = head
21         even = head
22         while r:
23             if pos % 2:
24                 even = r
25                 r = r.next
26             else:
27                 first_even = odd.next
28                 r_next = r.next
29                 odd.next = r
30                 r.next = first_even
31                 even.next = r_next
32                 odd = r
33                 r = r_next
34             pos += 1
35         return head

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理