目录

AaronJny

诗酒繁华,书剑天涯。

leetcode题解第24题 Swap Nodes in Pairs (两两交换链表中的节点)

题外话:之前说了写了代码也不一定会写题解,因为懒,然后我就真的没写……题目断断续续坚持在做,这代码都是好早之前写的了,题解嘛……果然,我就是个鸽子,咕咕咕。

image.png

反正你们应该也不需要我的题解,毕竟网上那么多,我就写着做个纪念。

image.png

好了,说正题。题目的大意是:

给定一个链表,你需要两两交换其中相邻的节点,并返回交换后的链表。但是你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

样例输入:

1->2->3->4

样例输出:

2->1->4->3

从示例可以看出,第一个节点和第二个节点做了交换,第三个节点和第四个节点做了交换。

leetcode 中的 python 链表是这样定义的:

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

这就是一个简单的模拟题,直接上代码吧,注释很详细:

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        """
        两两交换给定链表的节点
        :param head: 链表头结点
        :return:
        """
        # 如果链表为空,或链表长度为1,就不用交换了,直接返回
        if head is None or head.next is None:
            return head
        # p1作为一个游标,遍历整个链表,最开始指向头结点
        p1 = head
        # 现在last指定第三个节点
        last = p1.next.next
        # second指向第二个节点
        second = p1.next
        # 把第一个节点放到second后面去
        second.next = p1
        # 并且使 *前*第一个节点的next指向第三个节点last
        p1.next = last
        # 现在second是第一个节点,并且完成了第一个节点和第二个节点的交换
        head = second
        # 后面重复这个过程即可
        while p1.next:
            if p1.next.next is None:
                break
            first = p1.next
            second = first.next
            last = second.next
            p1.next = second
            second.next = first
            first.next = last
            p1 = first
        # 返回头节点
        return head

标题:leetcode题解第24题 Swap Nodes in Pairs (两两交换链表中的节点)
作者:AaronJny
地址:https://aaronjny.com/articles/2019/11/06/1573019415566.html