吹拉弹唱


  • Home
  • Archive
  • Categories
  • Tags
  • Books
  •  

© 2022 Kleon

Theme Typography by Makito

Proudly published with Hexo

算法基础 - 链表

Posted at 2021-03-12Updated at 2021-03-25 算法  算法 数据结构 leetcode 

表是最基础的数据结构之一，存储线性数据，内存结构不连续。

# 基础

链表可通过自定义数据结构，使用指针或引用指向前后节点。

Go提供了"container/list"1标准库实现双向链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package main

import (
  "container/list"
  "fmt"
)

func main() {
  // Create a new list and put some numbers in it.
  l := list.New()
  e4 := l.PushBack(4)
  e1 := l.PushFront(1)
  l.InsertBefore(3, e4)
  l.InsertAfter(2, e1)

  // Iterate through list and print its contents.
  for e := l.Front(); e != nil; e = e.Next() {
    fmt.Println(e.Value)
  }

}

# 实战

# 虚拟头结点移除链表中指定元素

移除链表元素

  • 基本链表操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeElements(head *ListNode, val int) *ListNode {
    vhead := &ListNode{0,head}
    head = vhead

    for head != nil && head.Next != nil {
        if head.Next.Val == val {
            head.Next = head.Next.Next
        } else {
            head = head.Next
        }
    }

    return vhead.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
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
77
78
79
80
81
82
type Node struct {
  Val  int
  Next *Node
}

type MyLinkedList struct {
  size int
  head *Node
}

/** Initialize your data structure here. */
func Constructor() MyLinkedList {
  return MyLinkedList{
    0,
    &Node{},
  }
}

/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
func (this *MyLinkedList) Get(index int) int {
    if index < 0 || index >= this.size {
        return -1
    }

  prev := this.head
  for i := 0; i < index; i++ {
    prev = prev.Next
  }
  return prev.Next.Val
}

/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
func (this *MyLinkedList) AddAtHead(val int) {
  this.AddAtIndex(0, val)
}

/** Append a node of value val to the last element of the linked list. */
func (this *MyLinkedList) AddAtTail(val int) {
  this.AddAtIndex(this.size, val)
}

/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
func (this *MyLinkedList) AddAtIndex(index int, val int) {
    if index < 0 || index > this.size {
        return
    }

  prev := this.head
  for i := 0; i < index; i++ {
    prev = prev.Next
  }
  node := &Node{Val: val}
  node.Next = prev.Next
  prev.Next = node

  this.size++
}

/** Delete the index-th node in the linked list, if the index is valid. */
func (this *MyLinkedList) DeleteAtIndex(index int) {
    if index < 0 || index >= this.size {
        return
    }

  prev := this.head
  for i := 0; i < index; i++ {
    prev = prev.Next
  }
  prev.Next = prev.Next.Next

  this.size--
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Get(index);
 * obj.AddAtHead(val);
 * obj.AddAtTail(val);
 * obj.AddAtIndex(index,val);
 * obj.DeleteAtIndex(index);
 */
  • 双向链表
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
type Node struct {
    Val int
    Next *Node
    Prev *Node
}

type MyLinkedList struct {
    Head *Node
    Tail *Node
    Length int
}

/** Initialize your data structure here. */
func Constructor() MyLinkedList {
    head := &Node{}
    tail := &Node{}
    head.Next = tail
    tail.Prev = head
    return MyLinkedList{
        Head: head,
        Tail: tail,
        Length: 0,
    }
}

func (this *MyLinkedList) Print(str string) {
    fmt.Printf("---%v---\n", str)
    pt := this.Head
    fmt.Printf("head %v\n", pt)
    for i := 0; i <= this.Length; i++{
        pt = pt.Next
        fmt.Printf("%v %v\n", i, pt)
    }
    pt = pt.Next
    fmt.Printf("tail %v\n", pt)
}


/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
func (this *MyLinkedList) Get(index int) int {
    if index >= this.Length {
        return -1
    }
    ret := this.Head
    for i := 0; i <= index; i++ {
        ret = ret.Next
    }
    return ret.Val
}


/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
func (this *MyLinkedList) AddAtHead(val int)  {
    node := &Node{
        Val: val,
        Next: this.Head.Next,
        Prev: this.Head,
    }
    this.Head.Next.Prev = node
    this.Head.Next = node

    if this.Tail.Prev.Prev == nil {
        this.Tail.Prev = this.Head.Next
    }
    this.Length++
    // this.Print("AddAtHead")
}


/** Append a node of value val to the last element of the linked list. */
func (this *MyLinkedList) AddAtTail(val int)  {
    node := &Node{
        Val: val,
        Next: this.Tail,
        Prev: this.Tail.Prev,
    }
    this.Tail.Prev.Next = node
    this.Tail.Prev = node
    if this.Head.Next.Next == nil {
        this.Head.Next = this.Tail.Prev
    }
    this.Length++
    // this.Print("AddAtTail")
}


/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
func (this *MyLinkedList) AddAtIndex(index int, val int)  {
    if index == this.Length {
        this.AddAtTail(val)
        return
    }

    if index < 0 {
        this.AddAtHead(val)
        return
    }

    var pt *Node
    pt = this.Head
    for i := 0; i <= index; i++ {
        pt = pt.Next
    }

    node := &Node{
        Val: val,
        Next: pt,
        Prev: pt.Prev,
    }
    pt.Prev.Next = node
    pt.Prev = node
    this.Length++
    // this.Print("AddAtIndex")
}


/** Delete the index-th node in the linked list, if the index is valid. */
func (this *MyLinkedList) DeleteAtIndex(index int)  {
    if index >= this.Length {
        return
    }

    if index < 0 {
        index = this.Length + index
    }

    var pt *Node
    pt = this.Head
    for i := 0; i <= index; i++ {
        pt = pt.Next
    }
    pt.Prev.Next = pt.Next
    pt.Next.Prev = pt.Prev
    this.Length--
    // this.Print("DeleteAtIndex")
}


/**
 * Your MyLinkedList object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Get(index);
 * obj.AddAtHead(val);
 * obj.AddAtTail(val);
 * obj.AddAtIndex(index,val);
 * obj.DeleteAtIndex(index);
 */

# 反转链表

反转链表

  • 构建新链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    pt := head
    var tail *ListNode
    for pt != nil {
        tail = &ListNode{
            pt.Val,
            tail,
        }
        pt = pt.Next
    }
    return tail
}
  • 双指针法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var pre, temp *ListNode
    cur := head
    for cur != nil {
        temp = cur.Next
        cur.Next = pre
        pre = cur
        cur = temp
    }
    return pre
}

# 环形链表的入环节点

环形链表
环形链表II

fast=x+y+n(y+z)fast = x + y + n(y + z) fast=x+y+n(y+z)

slow=x+yslow = x + y slow=x+y

fast=2slowfast = 2slow fast=2slow

x+y=n(y+z)x + y = n(y + z) x+y=n(y+z)

x=(n−1)(y+z)+zx = (n - 1)(y + z) + z x=(n−1)(y+z)+z

n = 1时， x = z

  • 快慢指针法
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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    fast := head
    slow := head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            p1 := fast
            p2 := head
            for p1 != p2 {
                p1 = p1.Next
                p2 = p2.Next
            }
            return p2
        }
    }
    return nil
}

# 删除排序链表中的重复元素 II

删除排序链表中的重复元素 II

  • 操作指针，开始指针，结束指针。注意绝对不重复的条件是开始指针和结束指针相邻且不相等。
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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil || head.Next == nil { return head }
    vhead := &ListNode{Next:head}
    cur := vhead
    start := vhead.Next
    end := vhead.Next.Next
    for start != nil && end != nil {
        if start.Val != end.Val {
            if end == start.Next {
                cur = cur.Next
            }
            start = end
            end = end.Next
        } else {
            end = end.Next
            cur.Next = end
        }
    }
    return vhead.Next
}
  • [1] Package list

Share 

 Previous post: 算法基础 - 排序 Next post: 算法基础 - 优先队列 

© 2022 Kleon

Theme Typography by Makito

Proudly published with Hexo