03.链表
# 01.链表反转
# 反转链表 (opens new window)
反转一个单链表。
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
1
2
2
# 1.1 python
#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
def list_reverse(head):
if head == None:
return None
L, R, cur = None, None, head # 左指针、有指针、游标
while cur.next != None:
L = R # 左侧指针指向以前右侧指针位置
R = cur # 右侧指针前进一位指向当前游标位置
cur = cur.next # 游标每次向前进一位
R.next = L # 右侧指针指向左侧实现反转
cur.next = R # 当跳出 while 循环时 cur(原链表最后一个元素) R(原链表倒数第二个元素)
return cur
if __name__ == '__main__':
'''
原始链表:1 -> 2 -> 3 -> 4
反转链表:4 -> 3 -> 2 -> 1
'''
lst = Node(1, Node(2, Node(3, Node(4)))) # 1-->2-->3-->4
l2 = list_reverse(lst) # 4-->3-->2-->1
print(l2.val) # 4
print(l2.next.val) # 3
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
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
# 1.2 golang
package main
import "fmt"
type ListNode struct {
Val int
Next *ListNode
}
func reverseList(head *ListNode) *ListNode {
if head == nil {
return nil
}
cur := head // 游标
var L, R *ListNode // 左指针、右指针
for cur.Next != nil {
L = R // 左侧指针指向以前右侧指针位置
R = cur // 右侧指针前进一位指向当前游标位置
cur = cur.Next // 游标每次向前进一位
R.Next = L // 右侧指针指向左侧实现反转
}
cur.Next = R // 当跳出 while 循环时 cur(原链表最后一个元素) R(原链表倒数第二个元素)
return cur
}
func main() {
l := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 3, Next: nil}}}
l1 := reverseList(l)
for l1 != nil {
fmt.Print(l1.Val, "\t") // 3 2 1
l1 = l1.Next
}
}
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
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
# 02.合并两个有序链表
# 2.1 题目描述
- 将两个升序链表合并为一个新的 升序 链表并返回。
- 新链表是通过拼接给定的两个链表的所有节点组成的。
输入:l1 = 1->2->4, l2 = 1->3->4
输出:1->1->2->3->4->4
1
2
2
# 2.2 python
- 我们可以用迭代的方法来实现上述算法。
- 当 l1 和 l2 都不是空链表时,判断 l1 和 l2 哪一个链表的头节点的值更小,将较小值的节点添加到结果里
- 当一个节点被添加到结果里之后,将对应链表中的节点向后移一位。
class ListNode:
def __init__(self,val=None, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1, l2):
head = ListNode(-1) # head是新链表的头部
cur = head # 我们维护一个cur 指针,我们需要做的是调整它的 next 指针
while l1 and l2: # 我们重复以下过程,直到 l1 或者 l2 指向了 null
# 如果l1值小就将l1节点加到新链表后面
if l1.val <= l2.val:
cur.next = l1
l1 = l1.next
# 否则,我们对 l2 做同样的操作
else:
cur.next = l2
l2 = l2.next
cur = cur.next # 不管我们将哪一个元素接在了后面,我们都需要把 prev 向后移一位
# 合并后 l1 和 l2 最多只有一个还未被合并完,我们直接将链表末尾指向未合并完的链表即可
cur.next = l1 if l1 is not None else l2
return head.next
l1 = ListNode(1,ListNode(2,ListNode(4))) # 1->2->4
l2 = ListNode(1,ListNode(3,ListNode(4))) # 1->3->4
l = mergeTwoLists(l1, l2)
while l:
print(l.val) # 1 1 2 3 4 4
l = l.next
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
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
# 2.3 golang
输入:l1 = 1->2->4, l2 = 1->3->4
输出:1->1->2->3->4->4
1
2
2
package main
import "fmt"
type ListNode struct {
Val int
Next *ListNode
}
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
head := &ListNode{Val: -1} // head是新链表的头部
cur := head // 我们维护一个cur 指针,我们需要做的是调整它的 next 指针
for list1 != nil && list2 != nil { // 我们重复以下过程,直到 l1 或者 l2 指向了 null
if list1.Val <= list2.Val { // 如果l1值小就将l1节点加到新链表后面
cur.Next = list1
list1 = list1.Next
} else { // 否则,我们对 l2 做同样的操作
cur.Next = list2
list2 = list2.Next
}
cur = cur.Next // 不管我们将哪一个元素接在了后面,我们都需要把 prev 向后移一位
}
// 合并后 l1 和 l2 最多只有一个还未被合并完,我们直接将链表末尾指向未合并完的链表即可
if list1 != nil {
cur.Next = list1
}
if list2 != nil {
cur.Next = list2
}
return head.Next
}
func main() {
l1 := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 3, Next: nil}}}
l2 := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 4, Next: nil}}}
l := mergeTwoLists(l1, l2)
for l != nil {
fmt.Print(l.Val, "\t")
l = l.Next
}
// 1 1 2 2 3 4
}
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
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
# 03.相交链表起点
# 3.1 题目描述
- 找到两个单链表相交的起始节点
# 3.2 python
- headA走的路径:4-》1-》8-》4-》 5-》0-》1-》8
- headB走的路径:5-》0-》1-》8-》4-》 4-》1-》8
- 可以看到,最终两个指针都会遍历完这两个链表,最终肯定会相遇
class ListNode:
def __init__(self, val=None, next=None):
self.val = val
self.next = next
def getNode(headA, headB):
p1 = headA
p2 = headB
while p1 != p2:
p1 = headB if p1 is None else p1.next # 如果p1链表到达末尾,p1=headB 继续遍历
p2 = headA if p2 is None else p2.next # 如果p2链表到达末尾,p2=headA 继续遍历
return p1
if __name__ == '__main__':
headA = ListNode(4)
n2 = ListNode(1)
n3 = ListNode(8) # 这个节点是相交节点
n4 = ListNode(4)
headA.next = n2
n2.next = n3
n3.next = n4
headB = ListNode(5)
n6 = ListNode(0)
n7 = ListNode(1)
headB.next = n6
n6.next = n7
n7.next = n3
print( getNode(headA, headB).val ) # 8
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
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
# 3.3 golang
package main
import "fmt"
type ListNode struct {
Val int
Next *ListNode
}
func getIntersectionNode(headA, headB *ListNode) *ListNode {
p1 := headA
p2 := headB
for p1 != p2 {
if p1 != nil {
p1 = p1.Next
}else {
p1 = headB // 如果p1链表到达末尾,p1=headB 继续遍历
}
if p2 != nil {
p2 = p2.Next
}else {
p2 = headA // 如果p2链表到达末尾,p2=headA 继续遍历
}
}
return p1
}
func main() {
headA := ListNode{Val: 4}
n2 := ListNode{Val: 1}
n3 := ListNode{Val: 8}
n4 := ListNode{Val: 4}
headA.Next = &n2
n2.Next = &n3
n3.Next = &n4
headB := ListNode{Val: 5}
n6 := ListNode{Val: 0}
n7 := ListNode{Val: 1}
headB.Next = &n6
n6.Next = &n7
n7.Next = &n3
l := getIntersectionNode(&headA, &headB)
fmt.Println(l.Val) // 8
}
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
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
# 04.环形链表
# 4.1 题目描述
给定一个链表,判断链表中是否有环。
# 4.2 python
- 快慢指针解决
- 慢指针每次走一步,快指针每次走两步
- 只要成环肯定快指针会和慢指针重合
class ListNode:
def __init__(self,val=None,next=None):
self.val = val
self.next = next
def hasCycle(head):
if not head or not head.next:
return False
slow = head # 慢指针每次走一步
fast = head.next # 快指针每次走两步
while slow != fast:
if not fast or not fast.next: # 如果快指针遍历结束,证明不成环
return False
slow = slow.next
fast = fast.next.next
return True
if __name__ == '__main__':
p1 = ListNode(1)
p2 = ListNode(2)
p3 = ListNode(0)
p4 = ListNode(-4)
p1.next = p2
p2.next = p3
p3.next = p4
p4.next = p2
print( hasCycle(p1) ) # True
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
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
# 4.3 golang
package main
import (
"fmt"
)
type ListNode struct {
Val int
Next *ListNode
}
func hasCycle(head *ListNode) bool {
if head == nil || head.Next == nil {
return false
}
slow := head // 慢指针每次走一步
fast := head.Next // 快指针每次走两步
for slow != fast {
if fast == nil || fast.Next == nil { // 如果快指针遍历结束,证明不成环
return false
}
slow = slow.Next
fast = fast.Next.Next
}
return true // 快慢指针相遇就跳出循环,返回True,证明成环
}
func main() {
head := ListNode{Val: 1}
p2 := ListNode{Val: 2}
p3 := ListNode{Val: 0}
p4 := ListNode{Val: -4}
head.Next = &p2
p2.Next = &p3
p3.Next = &p4
p4.Next = &p2
l := hasCycle(&head)
fmt.Println(l) // true
}
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
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
# 05.回文链表
# 5.1 题目描述
- 请判断一个链表是否为回文链表
输入: 1->2
输出: false
输入: 1->2->2->1
输出: true
1
2
3
4
5
2
3
4
5
# 5.2 python
- 使用快慢两个指针,快指针每次走两步,慢指针每次走一步
- 慢指针移动的时候同时定义L,R两个指针,将原始链表前半部分反转
- 当快指针走到链表尾部是,这个时候是这样的
- slow慢指针正好走到了原始链表中间位置
- R右指针正好将原始链表中间部分反转了
- 此时只需要一一对比是否每一个值是否相等即可
class ListNode:
def __init__(self,val=None,next=None):
self.val = val
self.next = next
def isHW(head):
L, R, slow = None, None, head
fast = head
while fast and fast.next:
fast = fast.next.next
# 反转链表
R = slow # 右指针向右走一步
slow = slow.next # 慢指针游标向右移动一位
R.next = L # 右指针的下一个节点指向左指针
L = R # 左指针向右移动一位
if fast: # 如果是偶数个,快指针还有一步没有走,所以需要再走一步
slow = slow.next # 最后slow就指向了链表中间位置
# 这是slow指针指向链表中间位置,R指针指向的是原始链表前半部分的反转头部
while slow and R:
if slow.val != R.val:
return False
slow = slow.next
R = R.next
return True
if __name__ == '__main__':
l = ListNode(1,ListNode(2,ListNode(2,ListNode(1))))
print( isHW(l) ) # True
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
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
# 5.3 golang
package main
import (
"fmt"
)
type ListNode struct {
Val int
Next *ListNode
}
func isPalindrome(head *ListNode) bool {
slow := head
fast := head
var L, R *ListNode
for fast != nil && fast.Next != nil {
fast = fast.Next.Next
// 反转链表
R = slow // 右指针向右走一步
slow = slow.Next // 慢指针游标向右移动一位
R.Next = L // 右指针的下一个节点指向左指针
L = R // 左指针向右移动一位
}
// 如果是偶数个,快指针还有一步没有走,所以需要再走一步
if fast != nil {
slow = slow.Next // 最后slow就指向了链表中间位置
}
// 这是slow指针指向链表中间位置,R指针指向的是原始链表前半部分的反转头部
for slow != nil && R !=nil {
if slow.Val != R.Val {
return false
}
slow = slow.Next
R = R.Next
}
return true
}
func main() {
head := ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 2, Next: &ListNode{Val: 1}}}}
l := isPalindrome(&head)
fmt.Println(l) // true
}
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
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
# 06.链表中倒数第k个节点
# 6.1 题目描述
- 输入一个链表,输出该链表中倒数第k个节点。
- 为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
1
2
2
# 6.2 python
这道题采用快慢指针的方式,定义一个计数器
fast指针先开始移动,当计数器走过K个数后,slow指针在开始移动。
class ListNode:
def __init__(self,val=None,next=None):
self.val = val
self.next = next
def getKthFromEnd(head, k):
slow = fast = head
n = 0
while fast:
# fast指针先开始移动,当计数器走过K个数后,slow指针在开始移动
if n>=k:
slow = slow.next
fast = fast.next
n += 1
return slow
if __name__ == '__main__':
root = ListNode(1,ListNode(2,ListNode(3,ListNode(4,ListNode(5)))))
print( getKthFromEnd(root, 2).val )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 6.3 golang
package main
import (
"fmt"
)
type ListNode struct {
Val int
Next *ListNode
}
func getKthFromEnd(head *ListNode, k int) *ListNode {
slow := head
fast := head
n := 0
for fast != nil {
// fast指针先开始移动,当计数器走过K个数后,slow指针在开始移动
if n >= k {
slow = slow.Next
}
fast = fast.Next
n += 1
}
return slow
}
func main() {
head := ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 3, Next: &ListNode{Val: 4}}}}
l := getKthFromEnd(&head, 2)
fmt.Println(l.Val) // 3
}
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
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
# 07.删除中间节点
# 7.1 题目描述
# 删除中间节点 (opens new window)
实现一种算法,删除单向链表中间的某个节点(即不是第一个或最后一个节点)
假定你只能访问该节点。
输入:单向链表a->b->c->d->e->f中的节点c
结果:不返回任何数据,但该链表变为a->b->d->e->f
1
2
2
# 7.2 python
def deleteNode(node):
node.val = node.next.val # 将这个需要删除的c,的值
node.next = node.next.next
1
2
3
2
3
# 08.两数相加
# 8.1 python
- 题目
- 给你两个
非空 的链表
,表示两个非负的整数
。 - 它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
- 请你将两个数相加,并以相同形式返回一个表示和的链表。
- 给你两个
输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[7,0,8]
解释:342 + 465 = 807
1
2
3
2
3
答案
- 1.先将l1和l2头节点的值加起来
赋值给新链表的头节点
- 2.遍历两个链表,只要有一个链表还没有遍历到末尾,就继续遍历
- 3.
每次遍历生成一个当前节点cur的下一个节点
,其值为两链表对应节点的和再加上当前节点cur产生的进位
- 4.更新进位后的当前节点cur的值
- 5.循环结束后,因为首位可能产生进位,因此如果cur.val是两位数的话,新增一个节点
- 6.返回头节点
- 1.先将l1和l2头节点的值加起来
class ListNode(object):
def __init__(self, val=None, next=None):
self.val = val
self.next = next
l1 = ListNode(1, ListNode(3, ListNode(3))) # 133
l2 = ListNode(1, ListNode(2)) # 12
def addTwoNumbers(l1, l2):
head = ListNode(l1.val + l2.val) # 赋值给新链表的头节点
cur = head # 新链表头部
while l1.next or l2.next: # 只要有一个链表还没有遍历到末尾,就继续遍历
l1 = l1.next if l1.next else ListNode(0) # 指针向下移动一位,如果链表已经遍历完那么就添加一个val为0的节点
l2 = l2.next if l2.next else ListNode(0)
# 在新链表添加一个元素,值为 两个链表节点的值 + 进位的值
cur.next = ListNode(l1.val + l2.val + cur.val // 10)
# 因为以前存入的节点值可能会大于10,所以对存入的值进行更新,区域即可
cur.val = cur.val % 10
# 指针指向新链表的下一个节点
cur = cur.next
# 遍历到最后一个节点时如果大于10,在进行一次进一操作
if cur.val >= 10:
cur.next = ListNode(cur.val // 10) # 新建一个节点存放进一的位
cur.val = cur.val % 10 # 将大于10的节点进行趋于后重新赋值
return head
l = addTwoNumbers(l1, l2)
print(l.val) # 2
print(l.next.val) # 5
print(l.next.next.val) # 3
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
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
# 8.2 golang
package main
import (
"fmt"
)
type ListNode struct {
Val int
Next *ListNode
}
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
head := &ListNode{Val: l1.Val+l2.Val} // 赋值给新链表的头节点
cur := head // 新链表头部
// 只要有一个链表还没有遍历到末尾,就继续遍历
for l1.Next != nil || l2.Next != nil {
// 指针向下移动一位,如果链表已经遍历完那么就添加一个val为0的节点
if l1.Next != nil {
l1 = l1.Next
}else {
l1 = &ListNode{Val: 0}
}
if l2.Next != nil {
l2 = l2.Next
}else {
l2 = &ListNode{Val: 0}
}
// 在新链表添加一个元素,值为 两个链表节点的值 + 进位的值
cur.Next = &ListNode{Val: l1.Val + l2.Val + cur.Val / 10}
cur.Val = cur.Val % 10 // 因为以前存入的节点值可能会大于10,所以对存入的值进行更新,区域即可
cur = cur.Next // 指针指向新链表的下一个节点
}
// 遍历到最后一个节点时如果大于10,在进行一次进一操作
if cur.Val >= 10 {
cur.Next = &ListNode{Val: cur.Val / 10} // 新建一个节点存放进一的位
cur.Val = cur.Val % 10 // 将大于10的节点进行趋于后重新赋值
}
return head
}
func main() {
l1 := &ListNode{Val: 2, Next: &ListNode{Val: 4, Next: &ListNode{Val: 3, Next: nil}}}
l2 := &ListNode{Val: 5, Next: &ListNode{Val: 6, Next: &ListNode{Val: 4, Next: nil}}}
l := addTwoNumbers(l1, l2)
for l != nil {
fmt.Print(l.Val, "\t")
l = l.Next // 7 0 8
}
}
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
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
# 09.重排链表
# 9.1 题目描述
# 重排链表 (opens new window)
给定一个单链表 L:L0→L1→…→Ln-1→Ln ,
将其重新排列后变为: L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
1
# 9.2 python
- 因为链表不支持下标访问,所以我们无法随机访问链表中任意位置的元素。
- 因此比较容易想到的一个方法是,我们利用线性表存储该链表
- 然后利用线性表可以下标访问的特点,直接按顺序访问指定元素,重建该链表即可。
#! /usr/bin/env python
# -*- coding: utf-8 -*-
class ListNode(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
def reorderList(head):
tmp = [] # 创建一个列表存放节点数据
node = head
while node:
tmp.append(node) # 将每个节点分别加入到列表中
node = node.next # 指针向下移动一位
l,r = 0,len(tmp)-1
while l < r:
tmp[l].next = tmp[r] # 将左指针的下一个节点设置为右指针对称位置
l = l+1 # 左指针向右移动一位
if l == r: # 如果左指针移动一位和右指针重合,证明节点为奇数个,此时已经到链表中心位置
break
tmp[r].next = tmp[l] # 设置右侧指针的下一个节点为左侧位置下一个节点
r = r - 1 # 右指针向左移动一位
tmp[l].next = None # 此时左右指针重合,设置节点中心位置的下一个节点为None
return head # 返回链表重组后的头部节点
lst = ListNode(1, ListNode(2, ListNode(3, ListNode(4)))) # 1-->2-->3-->4
l = reorderList(lst)
while l:
print(l.val) # 1 4 2 3
l= l.next
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
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
# 9.3 golang
package main
import (
"fmt"
)
type ListNode struct {
Val int
Next *ListNode
}
func reorderList(head *ListNode) {
tmp := []*ListNode{} // 创建一个列表存放节点数据
node := head
for node != nil {
tmp = append(tmp, node) // 将每个节点分别加入到列表中
node = node.Next // 指针向下移动一位
}
l,r := 0, len(tmp) - 1
for l < r {
tmp[l].Next = tmp[r] // 将左指针的下一个节点设置为右指针对称位置
l = l + 1 // 左指针向右移动一位
// 如果左指针移动一位和右指针重合,证明节点为奇数个,此时已经到链表中心位置
if l == r {
break
}
tmp[r].Next = tmp[l] // 设置右侧指针的下一个节点为左侧位置下一个节点
r = r - 1 // 右指针向左移动一位
}
tmp[l].Next = nil // 此时左右指针重合,设置节点中心位置的下一个节点为None
}
func main() {
// 1-->2-->3-->4
head := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 3, Next: &ListNode{Val: 4}}}}
reorderList(head)
// 1 4 2 3
for head != nil {
fmt.Print(head.Val, "\t")
head = head.Next
}
}
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
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
# 10.反转链表 II
# 10.1 题目描述
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
1
2
2
# 10.2 python
- 使用反转链表的解法,反转 left 到 right 部分以后,再拼接起来。
- 我们还需要记录 left 的前一个节点,和 right 的后一个节点。
- 第 1 步:先将待反转的区域反转;
- 第 2 步:把
pre
的next
指针指向反转以后的链表头节点,把反转以后的链表的尾节点的next
指针指向succ
。
class ListNode:
def __init__(self, val, next=None):
self.val = val
self.next = next
def reverseBetween(head, left, right):
newhead = ListNode(0) # 新建一个链表
newhead.next = head # 将新链表插入到以前链表的头部
count = 0
thestack = []
cur = newhead # 使用一个指针指向新链表头部
while count < left: # 只要指针 还没有到左侧分割位置就移动指针
count += 1 # 数量加一,以便保持count和cur指针一起移动
temp1 = cur # 保存m-1节点(left的前一个节点)
cur = cur.next # 指针向下移动一位
while count <= right: # 只要指针还没有到达right位置 就继续循环
thestack.append(cur) # 将需要反转的节点加入到栈中
count += 1 # count数量加一保持和指针移动一致
cur = cur.next # 指针向右移动一位
temp2 = cur # 保存n+1节点(right的后一个节点)
while thestack != []: # 只要栈不为空就继续弹出元素
temp1.next = thestack.pop() # 将栈中的元素依次弹出并添加到 left的后面
temp1 = temp1.next
temp1.next = temp2 # 栈为空时,证明要反转的数据反转完成,再把right后面部分数据拼接到链表
return newhead.next # 返回新链表的下一个位置,就是原有链表的头部
# 1--> 2-->3-->4 -->5
lst = ListNode(1, ListNode(2, ListNode(3, ListNode(4,ListNode(5)))))
l = reverseBetween(lst,2,4)
while l:
print(l.val) # 1--> 4-->3-->2 -->5
l= l.next
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
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
# 10.3 golang
package main
import (
"fmt"
)
type ListNode struct {
Val int
Next *ListNode
}
func reverseBetween(head *ListNode, left int, right int) *ListNode {
newHead := &ListNode{Val: 0} // 新建一个链表
newHead.Next = head // 将新链表插入到以前链表的头部
count := 0
theStack := []*ListNode{}
cur := newHead // 使用一个指针指向新链表头部
var temp1, temp2 *ListNode
for count < left { // 只要指针 还没有到左侧分割位置就移动指针
count += 1 // 数量加一,以便保持count和cur指针一起移动
temp1 = cur // 保存m-1节点(left的前一个节点)
cur = cur.Next // 指针向下移动一位
}
for count <= right { // 只要指针还没有到达right位置 就继续循环
theStack = append(theStack, cur) // 将需要反转的节点加入到栈中
count += 1 // count数量加一保持和指针移动一致
cur = cur.Next // 指针向右移动一位
}
temp2 = cur // 保存n+1节点(right的后一个节点)
fmt.Println(theStack, theStack != nil)
for len(theStack) != 0 { // 只要栈不为空就继续弹出元素
temp1.Next = theStack[len(theStack) - 1] // 将栈中的元素依次弹出并添加到 left的后面
theStack = theStack[:len(theStack)-1]
temp1 = temp1.Next
}
temp1.Next = temp2 // 栈为空时,证明要反转的数据反转完成,再把right后面部分数据拼接到链表
return newHead.Next // 返回新链表的下一个位置,就是原有链表的头部
}
func main() {
// 1--> 2-->3-->4 -->5
head := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 3, Next: &ListNode{Val: 4, Next: &ListNode{Val: 5}}}}}
l := reverseBetween(head, 2,4)
// 1 4 3 2 5
for l != nil {
fmt.Print(l.Val, "\t")
l = l.Next
}
}
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
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
编辑 (opens new window)
上次更新: 2024/3/13 15:35:10