题解 | 链表的奇偶重排

from itertools import count
# 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:
        # write code here
        # 尾插法节点顺序不变，删除链表中的元素
        # 双指针
        if head and head.next:
            # 偶数节点列表
            p1 = ListNode(0)
            # 奇数节点列表
            p2 = ListNode(0)
            count = 0
            # p4是p1的最后一个元素
            p4 = p1
            # p5是p2的最后一个元素
            p5 = p2
            while head:
                count += 1
                # p3保存当前节点的位置
                p3 = head
                head = head.next
                p3.next = None
                if 0 == count%2:
                    # 偶数
                    # 尾指针找到
                    p4.next = p3
                    p4 = p4.next
                else:               
                    # 奇数
                    p5.next = p3
                    p5 = p5.next
            p5.next = p1.next
            head = p2.next
        return head

1. 引入2个假的头节点p1，p2，分布对应偶数节点，奇数节点
2. 引入两个尾指针，p4，p5，始终指向p1，p2的最后一个元素
3. 临时保存即将删除的节点p3
4. 根据计数判断，p3插入p1或者p2的尾部
5. 最后将p1偶数节点的真实头指针接入p5的后面，构造出目标列表