算法训练之 -- 设计链表

设计链表

1. 思路

  你可以选择使用单链表或者双链表，设计并实现自己的链表。单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针引用。如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

  • MyLinkedList() 初始化 MyLinkedList 对象。
  • int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
  • void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
  • void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
  • void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
  • void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

707. 设计链表 - 力扣（LeetCode）

2.解法一 单向链表

  实现单向链表，即每个节点仅存储本身的值和后继节点。除此之外，我们还需要一个哨兵（sentinel）节点作为头节点，和一个 size 参数保存有效节点数。如下图所示。

img

  初始化时，只需创建头节点 head 和 size 即可。

  实现 get(index) 时，先判断有效性，再通过循环来找到对应的节点的值。如下图所示。

img

  实现 addAtIndex(index, val) 时，如果 index 是有效值，则需要找到原来下标为 index 的节点的前驱节点 pred，并创建新节点 to_add，将to_add 的后继节点设为 pred 的后继节点，将 pred 的后继节点更新为 to_add，这样就将 to_add 插入到了链表中。最后需要更新 size。这样的操作对于 index=0 也成立，如以下两张图所示。

img

img

  实现 addAtHead(val) 和 addAtTail(val) 时，可以借助 addAtIndex(index, val) 来实现。

  实现 deleteAtIndex(index)，先判断参数有效性。然后找到下标为 index 的节点的前驱节点 pred，通过将 pred 的后继节点更新为 pred 的后继节点的后继节点，来达到删除节点的效果。同时也要更新 size。如下图所示。

img

Python

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
class ListNode:

    def __init__(self, val):
        self.val = val
        self.next =None

class MyLinkedList:

    def __init__(self):
        self.size = 0
        self.head = ListNode(0) # 哨兵节点

    # 获取链表中下标为 index 的节点的值
    def get(self, index: int) -> int:   
        if index < 0 or index >= self.size:
            return -1

        cur = self.head
        for _ in range(index + 1):
            cur = cur.next

        return cur.val

	# 将一个值为 val 的节点插入到链表中第一个元素之前
    def addAtHead(self, val: int) -> None:  
        self.addAtIndex(0, val)

	
    # 插入到尾节点后
    def addAtTail(self, val: int) -> None: 
        self.addAtIndex(self.size, val)

    # 将一个值为 val 的节点插入到链表中下标为 index 的节点之前
    def addAtIndex(self, index: int, val: int) -> None: 
        if index > self.size:
            return

        index = max(0, index)   # 插入到头结点也可
        self.size += 1  # 更新size大小
        pred = self.head
        for _ in range(index):  # 定位到插入下标的前驱结点
            pred = pred.next

        to_add = ListNode(val)  # 创建新节点    
        to_add.next = pred.next # 加入节点
        pred.next = to_add

	# 删除指定下标的节点
    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return
        
        self.size -= 1  # 更新链表长度
        pred = self.head

        for _ in range(index):  # 定位到要删除节点的前驱节点
            pred = pred.next
        pred.next = pred.next.next




# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

C++

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
class MyLinkedList {
public:
    MyLinkedList() {
        this->size = 0;
        this->head = new ListNode(0);
    }
    
    // 获取链表中下标为 index 的节点的值
    int get(int index) {
        if(index < 0 || index >= size){
            return -1;
        }
        ListNode *cur = head;
        for(int i=0; i<=index; i++){
            cur = cur->next;
        }
        return cur->val;
    }
    
    // 将一个值为 val 的节点插入到链表中第一个元素之前
    void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    // 插入到尾节点后
    void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    // 将一个值为 val 的节点插入到链表中下标为 index 的节点之前
    void addAtIndex(int index, int val) {
        if(index > size){
            return;
        }
        index = max(0, index);
        size++;
        ListNode *pred = head;
        for (int i=0; i<index; i++){
            pred = pred->next;
        }
        ListNode *toAdd = new ListNode(val);
        toAdd->next = pred->next;
        pred->next = toAdd;
    }
    
    // 删除指定下标的节点
    void deleteAtIndex(int index) {
        if(index < 0 || index >= size){
            return;
        }
        size--;
        ListNode *pred = head;
        for(int i=0; i<index; i++){
            pred = pred->next;
        }
        ListNode *p = pred->next;
        pred->next = pred->next->next;
        delete p;
    }
    
private:
    int size;
    ListNode *head;
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

3.解法2 双向链表

  实现双向链表，即每个节点要存储本身的值，后继节点和前驱节点。除此之外，需要一个哨兵节点作为头节点 head 和一个哨兵节点作为尾节点 tail。仍需要一个 size 参数保存有效节点数。如下图所示。

img

  初始化时，只需创建头节点 head 和 size 即可。

  实现 get(index) 时，先判断有效性，然后再比较从 head 还是 tail 来遍历会比较快找到目标，然后进行遍历。如下图所示。

img

  实现 addAtIndex(index, val) 时，如果 index 是有效值，则需要找到原来下标为 index 的节点 succ 和前驱节点 pred，并创建新节点 to_add，再通过各自 prev 和 next 变量的更新来增加 to_add。最后需要更新 size。如以下两张图所示。

img

  实现 addAtHead(val) 和 addAtTail(val) 时，可以借助 addAtIndex(index, val) 来实现。

  实现 deleteAtIndex(index)，先判断参数有效性。然后找到下标为 index 的节点的前驱节点 pred 和后继节点 succ，再通过各自 prev 和 next 变量的更新来删除节点，来达到删除节点的效果。同时也要更新 size。如下图所示。

img

Python

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
class ListNode:

    def __init__(self, x):
        self.val = x
        self.next = None
        self.prev = None

class MyLinkedList:

    # 初始化链表
    def __init__(self):
        self.size = 0
        self.head, self.tail = ListNode(0), ListNode(0)
        self.head.next = self.tail
        self.tail.prev = self.head

    # 获取链表中下标为 index 的节点的值
    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1

        if index + 1 < self.size - index:   # 从头遍历
            curr = self.head
            for _ in range(index + 1):
                curr = curr.next
        else:                               # 从尾遍历
            curr = self.tail
            for _ in range(self.size - index):
                curr = curr.prev
        
        return curr.val

    # 将一个值为 val 的节点插入到链表中第一个元素之前
    def addAtHead(self, val: int) -> None:
        self.addAtIndex(0, val)
    
    # 插入到尾节点后
    def addAtTail(self, val: int) -> None:
        self.addAtIndex(self.size, val)

    # 将一个值为 val 的节点插入到链表中下标为 index 的节点之前
    def addAtIndex(self, index: int, val: int) -> None:
        if index > self.size:
            return

        index = max(0, index)
        if index < self.size - index:   # 从头遍历
            pred = self.head
            for _ in range(index):
                pred = pred.next
            succ = pred.next
        else:                           # 从尾遍历
            succ = self.tail
            for _ in range(self.size - index):
                succ = succ.prev
            pred = succ.prev
        
        self.size += 1
        # 双向链表指向
        to_add = ListNode(val)
        to_add.prev = pred
        to_add.next = succ
        pred.next = to_add
        succ.prev = to_add

    # 删除指定下标的节点
    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return
        if index < self.size - index:
            pred = self.head
            for _ in range(index):
                pred = pred.next
            succ = pred.next.next
        else:
            succ = self.tail
            for _ in range(self.size - index - 1):
                succ = succ.prev
            pred = succ.prev.prev

        self.size -= 1
        pred.next = succ
        succ.prev = pred


# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

C++

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
struct DLinkListNode{
    int val;
    DLinkListNode *prev, *next;
    DLinkListNode(int _val) : val(_val), prev(nullptr), next(nullptr) {}   // 构造函数 初始化成员变量
};

class MyLinkedList {
public:
    MyLinkedList() {
        this->size = 0;
        this->head = new DLinkListNode(0);
        this->tail = new DLinkListNode(0);
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int index) {
        if(index < 0 || index >= size){
            return -1;
        }
        DLinkListNode *curr;
        if(index + 1 < size - index){
            curr = head;
            for(int i=0; i<=index; i++){
                curr = curr->next;
            }
        } else{
            curr = tail;
            for(int i=0; i<size - index; i++){
                curr = curr->prev;
            }
        }
        return curr->val;
    }
    
    void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    void addAtIndex(int index, int val) {
        if(index > size){
            return;
        }
        index = max(0, index);
        DLinkListNode *pred, *succ;
        if(index < size - index){
            pred = head;
            for(int i=0; i<index; i++){
                pred = pred->next;
            }
            succ = pred->next;
        } else {
            succ = tail;
            for(int i=0; i < size - index; i++){
                succ = succ->prev;
            }
            pred = succ->prev;
        }
        size++;
        DLinkListNode *toAdd = new DLinkListNode(val);
        toAdd->prev = pred;
        toAdd->next = succ;
        pred->next = toAdd;
        succ->prev = toAdd;
    }
    
    void deleteAtIndex(int index) {
        if (index < 0 || index >= size){
            return;
        }
        DLinkListNode *pred, *succ;
        if (index < size - index) {
            pred = head;
            for (int i=0; i<index; i++){
                pred = pred->next;
            }
            succ = pred->next->next;
        } else {
            succ = tail;
            for (int i=0; i < size - index - 1; i++) {
                succ = succ->prev;
            }
            pred = succ->prev->prev;
        }
        size--;
        DLinkListNode *p = pred->next;
        pred->next = succ;
        succ->prev = pred;
        delete p;
    }
private:
    int size;
    DLinkListNode *head;
    DLinkListNode *tail;
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */
算法
#刷题
算法训练之 -- 设计链表
http://seulqxq.top/posts/21013/
作者
SeulQxQ
发布于
2024年1月25日
许可协议