链表的奇偶重排-牛客

思路

• 双指针
  指向奇索引的指针odd,
  指向偶索引的指针even
  注意：在循环前保存偶索引的头结点evenhead
  1、若链表为空，直接返回head，不需要重排。
  2、使用双指针odd和even分别遍历奇数节点和偶数节点，并给偶数节点链表一个头
  3、循环条件：因为even在后面，所以用even检查后两个元素是否为None，如果不为再进入循环。
  4、奇数最后一个节点后接循环开始前保存的偶数头结点，再返回head。

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
#
class Solution:
    def oddEvenList(self , head: ListNode) -> ListNode:
        # 双指针
        if head==None:
            return head
        #偶索引指针
        even=head.next
        #奇索引指针
        odd=head
        #指向偶索引开头
        evenhead=even
        while even and even.next:
            #odd连接even的后一位，即奇数位
            odd.next=even.next
            #odd进入下一个奇数位
            odd=odd.next
            #even连接后一个奇数的后一位，即偶数位
            even.next=odd.next
            #even进入下一个偶数位
            even=even.next
        #even整体连接在odd后面
        odd.next=evenhead
        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
30
31
32
33
34