【算法日常】链表节点两两交换

发布时间:2020-07-08 14:55:56 作者:wx5dcb7577ac572
来源:网络 阅读:163

链表节点两两交换

题目来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/swap-nodes-in-pairs

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.

本题考虑到量个两种解法:第一种用循环的方法去解答,第二种用递归的方式去解答,但是递归在前面的介绍说过,递归并不是最好的解法,相反递归还可能存在递归栈溢出的问题,而且递归比循环更加的耗费资源。这里是记录一下若用递归的解答方式该怎解答。

第一种解法 循环

循环方式解答,申请一个新的节点pre,将新的节点的next指向链表的开始部位。在使用一个tmp指针变量指向“需要交换的第一个节点”前面的节点。(第一组需要交换的节点的前一个节点当然是pre)
在使用start和end两个指针分别指向需要交换的第一个和第二个节点。
进行交换,将“本组需要交换的节点”的 前一个节点 的next指针指向“需要交换的第二个节点”
其次将 “本组需要交换的第一个节点”的next指针指向 “本组需要交换的第二个节点”的后面的那个节点
然后将 “本组需要交换的第二个节点”的next指针指向 "本组需要交换的第一个节点", 本次交换结束
最后将tmp的挪到下一组“需要交换的节点”的前一个节点,(即本次交换完成后的start节点)
当然交换过程可以用比较简洁的一行赋值语句进行,这里把他分开的原因是更清晰的展现交换的过程
时间复杂度 O(n), 空间复杂度 O(1)

代码如下:

# -*- coding: utf-8 -*-
# @Author   : xaohuihui
# @Time     : 19-12-12
# @File     : swap_pairs_linked.py
# Software  : study

"""
两两交换链表节点
"""

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

def swap_pairs(head: ListNode) -> ListNode:
    pre = ListNode(0)
    pre.next = head
    tmp = pre
        start = tmp.next  # “需要交换的第一个节点”
        end = tmp.next.next  # “需要交换的第二个节点”

        while tmp.next and tmp.next.next:
        tmp.next = end    # “需要交换的第一个节点”的前面的一个节点,指向需要交换的第二个节点
        start.next = end.next  # “需要交换的第一个节点”指向“需要交换的第二个节点”的后面的节点
        end.next = start   # “需要交换的第二个节点”指向“需要交换的第一个节点”
        # 上面交换完毕,现在start节点处于第二个节点的位置, end节点在第一个节点的位置
        tmp = start  # 将tmp指向下一组“需要交换的第一个节点”的前面的一个节点, 即本次交换完成的第二个节点的位置

    return pre.next

if __name__ == '__main__':
    node1 = ListNode(1)
    node2 = ListNode(2)
    node3 = ListNode(3)
    node4 = ListNode(4)
    node5 = ListNode(5)

    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node5

    result = swap_pairs(node1)

    while result:
        print(result.val)
        result = result.next

输出结果:

2
1
4
3
5
第二种解法 递归

递归解法,是将多组的交换抽象成一组交换,是先找到“本组需要交换的节点”的下一个节点
进行交换,“本组需要交换的第一个节点”的next指针指向“本组需要交换的第二个节点”的下一个节点
其次将“本组需要交换的第二个节点”的next指针指向 “本组需要交换的第一个节点”, 然后返回交换后的第一个节点(即交换前的第二个节点)

代码如下:

# -*- coding: utf-8 -*-
# @Author   : xaohuihui
# @Time     : 19-12-12
# @File     : swap_pairs_linked.py
# Software  : study

"""
两两交换链表节点
"""

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

def swap_pairs(head: ListNode) -> ListNode:
    if head is None or head.next is None:   # 当长度为奇数时返回最后一个节点,当长度为偶数的时候返回None
        print(head.val if head else head)
        return head

    pre = head.next  # head 为“第一个需要交换节点”, pre 为“第二个需要交换的节点”
    print(head.val, pre.val)
    head.next = swap_pairs(pre.next)  # “第一个需要交换的节点” 指向 “第二个需要交换的节点”的后面的节点
    pre.next = head  # “第二个需要交换的节点” 指向 “第一个需要交换的节点”
    print("swap", head.val, pre.val, head.next.val if head.next else head.next)
    return pre

if __name__ == '__main__':
    node1 = ListNode(1)
    node2 = ListNode(2)
    node3 = ListNode(3)
    node4 = ListNode(4)
    node5 = ListNode(5)

    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node5

    result = swap_pairs(node1)

    while result:
        print(result.val)
        result = result.next

输出结果:

1 2
3 4
5
swap 3 4 5
swap 1 2 4
2
1
4
3
5
推荐阅读:
  1. 【算法日常】K个一组反转链表
  2. 【算法日常】判断环形链表

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

算法 链表

上一篇:解决 jQuery UI Datepicker 无法弹出

下一篇:建网站应该选虚拟主机还是服务器呢

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》