刚开始准备刷算法题目的时候,感觉真的是好难,十道题目有九道是不会的。心中曾一万只草泥马跑过,自己怎么这么辣鸡。
慢慢得,我发现算法也是一个可以通过练习慢慢成长的。
废话不多说了,开始进入今天的正文,LeetCode链表知识点&题型总结
链表(Linked List)是一种常见的线性结构。它不需要一块连续的内存空间,通过指针即可将一组零散的内存块串联起来。我们把内存块成为链表的节点,为了将所有的节点串起来,每个链表的节点除了存储数据之外,还需要记录链表的下一个节点的地址,这个记录下个节点地址的指针我们叫做后驱指针。搜索链表需要O(N)的时间复杂度,这点和数组类似,但是链表不能像数组一样,通过索引的方式以O(1)的时间读取第n个数。链表的优势在于能够以较高的效率在任意位置插入或者删除一个节点。
每个节点有一个next指针指向后一个节点,还有一个成员变量用于存储数值。单向链表中有两个节点比较特殊,分别是头结点和尾节点。头结点用来记录链表的基地址,知道头结点我们就可以遍历得到整条链表。尾结点的特殊在于指针指向的是一个空指针NULL。
循环链表是一种特殊的单链表,与单链表不同的是尾节点不指向空地址,指向链表的头结点。优点是从链尾到链头比较方便,当要处理的数据具有环形结构特点是,非常适合用循环链表来处理。
双向链表支持两个方向,每个节点不只有一个后驱指针next指向后面的节点,还有一个前驱指针prev指向前面的节点。
时间复杂度 | 数组 | 链表 |
---|---|---|
插入删除 | O(n) | O(1) |
随机访问 | O(1) | O(n) |
无论这两个节点的相对位置和绝对位置如何,以上的处理方式均可成立
Given ÷ list: 1->2->3->4->5, and n = 2. 删除链表中导数第二个节点,变成1->2->3->5.
Java
class Solution{
public static ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy;
ListNode slow = dummy;
while(fast.next != null){
if(n <= 0)
slow = slow.next;
fast = fast.next;
n--;
}
if(slow.next != null)
slow.next = slow.next.next;
return dummy.next;
}
}
Leetcode中包含删除类的题目:
序号 | 题目 | 难度 | 代码 |
---|---|---|---|
19 | Remove Nth Node From End of List | medium | java |
82 | Remove Duplicates from Sorted List II | Medium | java |
83 | Remove Duplicates from Sorted List | Easy | java |
203 | Remove Linked List Elements | Easy | java |
237 | Delete Node in a Linked List | Easy | java |
最基础最常在面试中遇到的提醒,206一定要熟练掌握
/*迭代写法*/
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null){
return head;
}
ListNode dummy = null;
while (head != null){
ListNode next = head.next;
head.next = dummy;
dummy = head;
head = next;
}
return dummy;
}
}
/*递归写法*/
class Solution{
public ListNode reverseList(ListNode head) {
return reverseListHelper(head, null);
}
private ListNode reverseListHelper(ListNode head, ListNode newHead) {
if (head == null)
return newHead;
ListNode next = head.next;
head.next = newHead;
return reverseListHelper(next, head);
}
}
2、将p后面的元素删除,然后添加到g的后面。也即头插法。 3、根据m和n重复步骤(2) 4、返回dummyHead.next
/*迭代法*/
class Solution{
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode g = dummyHead;
ListNode p = dummyHead.next;
int step = 0;
while (step < m - 1) {
g = g.next; p = p.next;
step ++;
}
for (int i = 0; i < n - m; i++) {
ListNode removed = p.next;
p.next = p.next.next;
removed.next = g.next;
g.next = removed;
}
return dummyHead.next;
}
}
/*递归法*/
class Solution {
private boolean stop;
private ListNode left;
public void recurseAndReverse(ListNode right, int m, int n) {
if (n == 1) {
return;
}
right = right.next;
if (m > 1) {
this.left = this.left.next;
}
this.recurseAndReverse(right, m - 1, n - 1);
if (this.left == right || right.next == this.left) {
this.stop = true;
}
if (!this.stop) {
int t = this.left.val;
this.left.val = right.val;
right.val = t;
this.left = this.left.next;
}
}
public ListNode reverseBetween(ListNode head, int m, int n) {
this.left = head;
this.stop = false;
this.recurseAndReverse(head, m, n);
return head;
}
}
复杂度 | 迭代法 | 递归法 |
---|---|---|
时间复杂度 | O(N) | O(N) |
空间复杂度 | O(1) | O(N) |
序号 | 题目 | 难度 | 代码 |
---|---|---|---|
25 | Reverse Nodes in k-Group | Hard | java |
61 | Rotate List | Medium | java |
92 | Reverse Linked List II | Medium | java |
206 | Reverse Linked List | Easy | java |
Java
/*迭代法*/
class Solution{
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head = new ListNode(0);
ListNode cur = head;
while (l1 != null && l2 != null) {
if (l1.val >= l2.val) {
cur.next = l2;
l2 = l2.next;
} else {
cur.next = l1;
l1 = l1.next;
}
cur = cur.next;
}
if (l1 != null)
cur.next = l1;
if (l2 != null)
cur.next = l2;
return head.next;
}
}
/*递归法*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val > l2.val) {
ListNode tmp = l2;
tmp.next = mergeTwoLists(l1, l2.next);
return tmp;
} else {
ListNode tmp = l1;
tmp.next = mergeTwoLists(l1.next, l2);
return tmp;
}
}
}
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length == 0) return null;
return partion(lists, 0, lists.length - 1);
}
private ListNode partion(ListNode[] lists, int start, int end) {
if(start == end) {
return lists[start];
}
else if(start < end) {
int mid = (start + end) / 2;
ListNode l1 = partion(lists, start, mid);
ListNode l2 = partion(lists, mid + 1, end);
return merge(l1, l2);
}
else {
//not gonna happen.
return null;
}
}
private ListNode merge(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val < l2.val) {
l1.next = merge(l1.next, l2);
return l1;
} else {
l2.next = merge(l1, l2.next);
return l2;
}
}
}
LeetCode中包含 合并链表类的题目:
序号 | 题目 | 难度 | 代码 |
---|---|---|---|
2 | Add Two Numbers | medium | java |
21 | Merge Two Sorted Lists | Easy | java |
23 | Merge k Sorted Lists | Hard | java |
445 | Add Two Numbers II | Medium | java |
Java
public class Solution {
public boolean hasCycle(ListNode head) {
if(head==null) return false;
ListNode slow = head;
ListNode fast = head;
while(fast.next!=null && fast.next.next!=null) {
slow = slow.next;
fast = fast.next.next;
if(slow==fast) return true;
}
return false;
}
}
LeetCode中含有环形链表的题目:
序号 | 题目 | 难度 | 代码 |
---|---|---|---|
141 | Linked List Cycle | Easy | java |
142 | Linked List Cycle II | Medium | java |
708 | Insert into a Cyclic Sorted List | Medium | java |
Java
class Solution {
public boolean search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (target == nums[mid]) return true;
if (nums[mid] == nums[left]) left++;
else if (nums[mid] > nums[left]) {
if (nums[left] <= target && nums[mid] > target) right = mid - 1;
else left = mid + 1;
} else {
if (nums[mid] < target && target <= nums[right]) left = mid + 1;
else right = mid - 1;
}
}
return false;
}
}
LeetCode中含有拆分类的题目:
序号 | 题目 | 难度 | 代码 |
---|---|---|---|
725 | Split Linked List in Parts | Medium | java |
---- | ------------------------------------------------------------ | ------ | ----------------- |
86 | Partition List | Medium | java |
Input: 4->2->1->3 Output: 1->2->3->4
Java
public class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null)
return head;
// step 1.把链表分成两半
ListNode prev = null, slow = head, fast = head;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null;
// step 2.对于每一部分的链表进行排序
ListNode l1 = sortList(head);
ListNode l2 = sortList(slow);
// step 3. 合并 l2 和 l2
return merge(l1, l2);
}
ListNode merge(ListNode l1, ListNode l2) {
ListNode l = new ListNode(0), p = l;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
p.next = l1;
l1 = l1.next;
} else {
p.next = l2;
l2 = l2.next;
}
p = p.next;
}
if (l1 != null)
p.next = l1;
if (l2 != null)
p.next = l2;
return l.next;
}
}
LeetCode中 包含链表排序的题目:
序号 | 题目 | 难度 | 代码 |
---|---|---|---|
143 | Reorder List | Medium | java |
---- | ------------------------------------------------------------ | ------ | ----------------- |
147 | Insertion Sort List | Medium | java |
148 | Sort List | Medium | java |
链表的问题是面试当中常常会问到的,比如链表的倒置,删除链表中某个结点,合并两个排序链表,合并 k 个排序链表,排序两个无序链表等。
这些题目一般有一些相应的技巧可以解决。
第一,引入哨兵结点。如我们开头说的 dummy node 结点。在任何时候,不管链表是不是空,head结点都会一直指向这个哨兵结点。我们也把这种有哨兵结点的链表叫做带头链表。
第二,双指针法。这种用法适用于查找链表中某个位置,判断链表是否有环等
第三,分之归并法。这种用法适用于链表的排序处理,如合并 k 个排序链表,排序两个无序链表等。
第四,在解答的过程中,要多考虑边界情况。
参考资料:
1.https://leetcode-cn.com/problems/sort-list/discuss/46714/Java-merge-sort-solution
2.https://leetcode-cn.com/problems/merge-two-sorted-lists/discuss/9735/Python-solutions-(iteratively-recursively-iteratively-in-place).