Python中链表的奇偶重排操作

2023-04-11 00:00:00 链表 重排 奇偶

链表的奇偶重排操作就是将链表中的所有奇数节点放在偶数节点前面。实现这个操作的方法是：

  1. 遍历一遍链表，将奇数节点和偶数节点分别放到两个链表中。

  2. 将奇数链表的尾节点指向偶数链表的头节点。

下面是Python实现代码：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def oddEvenList(head: ListNode) -> ListNode:
    if not head:
        return head

    odd = head
    even = head.next
    evenHead = even
    while even and even.next:
        odd.next = odd.next.next
        even.next = even.next.next
        odd = odd.next
        even = even.next

    odd.next = evenHead

    return head

例子：

链表 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None

执行操作 oddEvenList(head)，得到的结果是链表 1 -> 3 -> 5 -> 2 -> 4 -> 6 -> None。

相关文章