算法与数据结构基础 - 链表(Linked List)

链表基础

链表(Linked List)相比数组(Array)，物理存储上非连续、不支持O(1)时间按索引存取；但链表也有其优点，灵活的内存管理、允许在链表任意位置上插入和删除节点。单向链表结构一般如下：

    //Definition for singly-linked list.

    struct ListNode {

        int val;

        ListNode *next;

        ListNode(int x) : val(x), next(NULL) {}

    };

相关LeetCode题：

707. Design Linked List 题解

237. Delete Node in a Linked List 题解

链表增删改查

要完成链表节点的查找、插入、删除与修改，需要特别留意前后指针的修改、空指针的处理。总得来说链表增删改查分三步：1/定义结束条件(一般为到达链表尾) 2/遍历链表 3/遍历过程中完成增删改查。

一些情况下会用哑节点(dummy node)来更方便对链表增删改查，这有时可以减少代码量。比如 LeetCode题目 203. Remove Linked List Elements：

    // 203. Remove Linked List Elements

    ListNode* removeElements(ListNode* head, int val) {

        ListNode* dummy=new ListNode();

        dummy->next=head;

        ListNode* cur=dummy;

        while(cur->next!=NULL){

            if(cur->next->val==val) cur->next=cur->next->next;

            else cur=cur->next;

        }

        return dummy->next;

    }

以上如果不使用dummy node，如果head是要被删除的节点，则需要特殊判断和处理，使用dummy node则化解了这个问题。

相关LeetCode题：

203. Remove Linked List Elements 题解

876. Middle of the Linked List 题解

83. Remove Duplicates from Sorted List 题解

82. Remove Duplicates from Sorted List II 题解

86. Partition List 题解

328. Odd Even Linked List 题解

1019. Next Greater Node In Linked List 题解

817. Linked List Components 题解

1171. Remove Zero Sum Consecutive Nodes from Linked List 题解

也可以用递归的方式遍历链表，但这种方式会重复访问节点，时间复杂度比O(n)高很多。

相关LeetCode题：

24. Swap Nodes in Pairs 题解

234. Palindrome Linked List 题解

反转/旋转链表

反转(reverse)链表与旋转(rotate)链表是考量链表操作的经典题目，最是考验做题人对链表节点逻辑关系的了解程度和是否能灵活处理指针。

相关LeetCode题：

206. Reverse Linked List 题解

92. Reverse Linked List II 题解

61. Rotate List 题解

25. Reverse Nodes in k-Group 题解

143. Reorder List 题解

环形链表

处理环形链表问题，常常用到双指针(Two Pointers)、快慢指针，例如 LeetCode题目 141. Linked List Cycle：

    // 141. Linked List Cycle

    bool hasCycle(ListNode *head) {

        if(head==NULL) return false;

        ListNode* p=head;

        ListNode* pp=head;

        while(pp->next!=NULL&&pp->next->next!=NULL){

            p=p->next;

            pp=pp->next->next;

            if(p==pp) return true;

        }

        return false;

    }

相关LeetCode题：

141. Linked List Cycle 题解

142. Linked List Cycle II 题解

708. Insert into a Cyclic Sorted List 题解

多链表处理

多链表的增删改、合并，与单链表的处理方式一样，只是增加了对多个链表的遍历。

21. Merge Two Sorted Lists 题解

2. Add Two Numbers 题解

445. Add Two Numbers II 题解

23. Merge k Sorted Lists 题解

链表排序

对链表进行排序一般指原址排序，即修改节点指针指向、而不修改节点的值。对链表进行归并排序(Merge Sort)，平均时间复杂度为O(nlogn)，相比其他排序方法，归并排序在平均时间复杂度上是较优的方法。

相关LeetCode题：

147. Insertion Sort List 题解

148. Sort List 题解

巴特西

算法与数据结构基础 - 链表(Linked List)

最新文章

热门文章