Python中链表的按照奇偶位置分离为两个链表

2023-04-11 00:00:00 链表分离奇偶

下面是Python代码实现：

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

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

    odd = head
    even = head.next
    evenHead = even # 记录偶数链表的头节点

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

    # 拼接奇偶链表
    odd.next = evenHead

    return head

具体解释如下：

定义一个链表节点类，包含节点值和指向下一个节点的指针。每个节点的值初始化为0，指针指向None。
定义oddEvenList函数，接受一个链表的头节点作为参数，并返回重新排列后的链表头节点。
如果链表为空或只有一个节点，直接返回原链表。
初始化奇数链表的头节点odd为head节点，偶数链表的头节点even为head节点的下一个节点。
记录偶数链表的头节点evenHead，以便最后把奇数链表和偶数链表拼接在一起。
只要偶数链表的下一个节点不为空，就将奇数链表的下一个节点指向偶数链表的下一个节点，奇数链表的指针往后移动一位，偶数链表的下一个节点指向偶数链表的下一个节点的下一个节点，偶数链表的指针往后移动一位。
完成奇偶链表分离后，把奇数链表的尾节点指向偶数链表的头节点。
返回排列后的链表头节点。

范例：

# 构造链表 1 -> 2 -> 3 -> 4 -> 5 -> None
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
# 对链表进行奇偶分离
newHead = oddEvenList(head)
# 输出奇偶分离后的链表中的奇数节点部分
while newHead:
    print(newHead.val)
    newHead = newHead.next
# 输出奇偶分离后的链表中的偶数节点部分
while head.next:
    head = head.next
    print(head.val)

输出结果：

相关文章