-
Notifications
You must be signed in to change notification settings - Fork 0
/
24.两两交换链表中的节点.py
77 lines (64 loc) · 1.77 KB
/
24.两两交换链表中的节点.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#
# @lc app=leetcode.cn id=24 lang=python3
#
# [24] 两两交换链表中的节点
#
# https://leetcode-cn.com/problems/swap-nodes-in-pairs/description/
#
# algorithms
# Medium (64.48%)
# Likes: 423
# Dislikes: 0
# Total Accepted: 74.2K
# Total Submissions: 115.1K
# Testcase Example: '[1,2,3,4]'
#
# 给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
#
# 你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
#
#
#
# 示例:
#
# 给定 1->2->3->4, 你应该返回 2->1->4->3.
#
#
#
# @lc code=start
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
# 递归
# class Solution:
# def swapPairs(self, head: ListNode) -> ListNode:
# if head == None or head.next == None:
# return head
# first = head
# second = head.next
# first.next = self.swapPairs(second.next)
# second.next = first
# return second
# 迭代
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
# 创建虚拟节点,当做head的前面一个节点
dummpNode = ListNode(-1)
dummpNode.next = head
preNode = dummpNode
# 保证要交换位置的两个node都存在
while head and head.next:
# 取出要交换的两个node
firstNode = head
secondNode = head.next
# 进行交换
preNode.next = secondNode
firstNode.next = secondNode.next
secondNode.next = firstNode
# 继续交换接下来两个,并且保存前一个node
head = firstNode.next
preNode = firstNode
return dummpNode.next
# @lc code=end