forked from yingl/LintCodeInPython
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathswap_two_nodes_in_linked_list.py
More file actions
54 lines (52 loc) · 1.77 KB
/
swap_two_nodes_in_linked_list.py
File metadata and controls
54 lines (52 loc) · 1.77 KB
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
# -*- coding: utf-8 -*-
class Solution:
# @param {ListNode} head, a ListNode
# @oaram {int} v1 an integer
# @param {int} v2 an integer
# @return {ListNode} a new head of singly-linked list
def swapNodes(self, head, v1, v2):
# Write your code here
dummy_node = ListNode(0)
dummy_node.next = head
v1_prev, v1_node = self.findNode(dummy_node, v1)
v2_prev, v2_node = self.findNode(dummy_node, v2)
'''
难点在下面，因为不能直接交换两个元素的值，
要特别小心类似v1_node.next等于v2_node的情况。
两种具体分析如下：
1. p1->v1->v2->n2 => p1->v2->v1->n2
- p1->v2 (tmp = n2)
- p1->v2->v1
- p1->v2->v1->n2(tmp)
2. p2->v2->v1->n1 => p2->v1->v2->n1
- p2->v2->v2 (tmp = v2)
- p2->v2->n1
- p2->v1
- p2->v1->v2->n1
对于普通情况
1. p1->v1->n1->p2->v2->n2
- p1->v2 (tmp = n2)
- p1->v2->n1
- p2->n1
- p2->n1->n2
2. p2->v2->n2->p1->v1->n2
- 类似上面
整个比较精妙的地方在于用dummy_node解决v1/v2可能是head的问题。
'''
if v1_node and v2_node:
v1_prev.next = v2_node
tmp = v2_node.next
if v1_node.next == v2_node:
v2_node.next = v1_node
v1_node.next = tmp
else:
v2_node.next = v1_node.next
v2_prev.next = v1_node
v1_node.next = tmp
return dummy_node.next
def findNode(self, head, val):
while head.next:
if head.next.val == val:
return head, head.next
head = head.next
return None, None