奇数结点升序偶数结点降序的单链表排序（Python实现）

题目

一个链表，奇数结点升序，偶数结点降序，要求变成一个全升序的链表。

例如：1->8->2->7->3->6->4->5，变为1->2->3->4->5->6->7->8

解析

按照以下步骤处理：

按照奇偶位拆分为两个链表
反转偶数结点构成的链表
合并两个递增链表

Python实现

# -*- coding:utf-8 -*-

class Node(object):

    def __init__(self, val=None, next=None):

        self.val = val

        self.next = next

def init_list(l):

    """创建不带头结点的单链表"""

    head = Node()

    tail = head

    for val in l:

        tail.next = Node(val)

        tail = tail.next

    tail.next = None

    return head.next

def split_list(head):

    """按照奇偶位拆分为两个链表"""

    head1 = head2 = None

    cur1 = cur2 = None

    count = 1

    while head:

        if count % 2 == 1:

            if cur1:

                cur1.next = head

                cur1 = cur1.next

            else:

                cur1 = head1 = head

        else:

            if cur2:

                cur2.next = head

                cur2 = cur2.next

            else:

                cur2 = head2 = head

        head = head.next

        count += 1

    cur1.next = None

    cur2.next = None

    return head1, head2

def reverse_list(head):

    """反转链表"""

    if not head or not head.next:

        return head

    pre = next = None

    while head:

        next = head.next

        head.next = pre

        pre = head

        head = next

    return pre

def merge_list(head1, head2):

    """合并两个递增链表"""

    head = Node()  # 设置一个临时结点

    tail = head

    while head1 and head2:

        if head1.val <= head2.val:

            tail.next = head1

            head1 = head1.next

        else:

            tail.next = head2

            head2 = head2.next

        tail = tail.next

    # 合并剩余结点

    if head1:

        tail.next = head1

    if head2:

        tail.next = head2

    return head.next

def visit_list(head):

    while head:

        print(head.val)

        head = head.next

if __name__ == '__main__':

    head = init_list([1, 8, 2, 7, 3, 6, 4, 5])  # 创建一个不带头结点的单链表：1->8->2->7->3->6->4->5

    head1, head2 = split_list(head)  # 1.按照奇偶位拆分为两个链表

    head2 = reverse_list(head2)      # 2.反转偶数结点构成的链表

    head = merge_list(head1, head2)  # 3.合并两个递增链表

    visit_list(head)  # 遍历链表

巴特西

奇数结点升序偶数结点降序的单链表排序（Python实现）

题目

解析

Python实现

最新文章

热门文章