您好,登录后才能下订单哦!
题目来源:力扣(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
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。