Python教程

Python编程题49--两两交换链表中的节点

本文主要是介绍Python编程题49--两两交换链表中的节点,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目

给定一个链表,请在不修改节点内部值的情况下,两两交换其中相邻的节点,并返回交换后链表的头节点。

例如:

原链表转换为列表:[1, 2, 3, 4]
最终的链表转换为列表:[2, 1, 4, 3]

原链表转换为列表:[1, 2, 3, 4, 5]
最终的链表转换为列表:[2, 1, 4, 3, 5]

原链表转换为列表:[]
最终的链表转换为列表:[]

已知 链表节点的定义、链表与列表相互转换 的代码如下:

class ListNode:  # 单链表
    def __init__(self, val=0, next=None):
        self.val = val  # 链表节点上存储的元素
        self.next = next  # 指向下一个链表节点


def list_to_list_node(numbers):  # 将列表转换为单向链表,并返回链表的头节点
    dummy_head = ListNode(0)
    pre = dummy_head
    for number in numbers:
        pre.next = ListNode(number)
        pre = pre.next
    pre = dummy_head.next
    return pre


def list_node_to_list(node):  # 将单向链表转换为列表
    result = []
    while node:
        result.append(node.val)
        node = node.next
    return result

实现思路

  • 假设初始链表节点如下:节点1 -> 节点2 -> 节点3 -> 节点4 -> 节点5,设置一个虚拟头节点后,链表变为:虚拟头节点 -> 节点1 -> 节点2 -> 节点3 -> 节点4 -> 节点5
  • 首先,需用3个变量保存在除虚拟头节点外的前3个节点,因为等会需要改变节点的指向
  • 第一步,让当前节点通过 next 指向节点2
  • 第二步,让当前节点的下个节点通过 next 指向节点1
  • 第三步,让当前节点的下下个节点通过 next 指向节点3
  • 第四步,让当前节点移动2位,也就是到 节点1 的位置,以便继续交换后面的节点
  • 通过上面几步处理后,链表变为:虚拟头节点 -> 节点2 -> 节点1 -> 节点3 -> 节点4 -> 节点5,同时当前节点已经变为 节点1
  • 循环以上几步操作,直到当前节点的下个节点或下下个节点出现空时,说明节点交换完成,最终得到的链表为:虚拟头节点 -> 节点2 -> 节点1 -> 节点4 -> 节点3 -> 节点5
  • 最后,将链表虚拟头节点的下一个节点,也就是将 节点2 返回即可

代码实现--迭代

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        dummy_head = ListNode(next=head)  # 设置虚拟头节点
        cur = dummy_head
        while cur.next is not None and cur.next.next is not None:
            tmp1, tmp2, tmp3 = cur.next, cur.next.next, cur.next.next.next  # 临时节点1、节点2、节点3
            cur.next = tmp2  # 改变节点指向,当前节点通过 next 指向节点2
            cur.next.next = tmp1  # 改变节点指向,下个节点通过 next 指向节点1
            cur.next.next.next = tmp3  # 改变节点指向,下下个节点通过 next 指向节点3
            cur = cur.next.next  # 当前节点移动2位(变为节点1)
        return dummy_head.next

代码实现--递归

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        cur = head
        while cur is None or cur.next is None:  # 递归终止条件:当前节点或下个节点为空
            return cur
        post = cur.next  # 临时保存下个节点
        cur.next = self.swapPairs(post.next)  # 改变节点指向,当前节点通过 next 指向经过递归处理的子链表
        post.next = cur  # 改变节点指向,下个节点通过 next 指向当前节点
        return post  # 每次递归调用后,当前节点和下个节点指向发生改变,子链表都是从下个节点开始

更多Python编程题,等你来挑战:Python编程题汇总(持续更新中……)

这篇关于Python编程题49--两两交换链表中的节点的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!