051、面试必刷TOP101--链表（230503）

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

提示：

本章节全部基于牛客网的题库中的在线编程，面试必刷TOP101：01-链表，总共十六道题目。

---

提示：以下是本篇文章正文内容，下面案例可供参考

链表

---

1、BM1 反转链表

题目描述：

给定一个单链表的头结点，长度为n，反转该链表后，返回新链表的表头。

• 0≤n≤1000
• 要求空间复杂度O（1）、时间复杂度O（1）

代码如下：

public class BM1 {/*** @param head : 给定一个链表的头节点* @return 返回反转链表后的新的头节点*/public ListNode ReverseList(ListNode head) {// base caseif (head == null || head.next == null) {return head;}// 利用指针(pre，记录之前遍历过的节点，cur为当前正在操作的节点，next保存原始链表顺序ListNode pre = null, cur = head, next = null;while (cur != null) {next = cur.next;cur.next = pre;pre = cur;cur = next;}return pre;}
}

总结：

其实，这道题很经典但是在设置指针的时候很容易出错，需要熟练使用指针。确保将一个指针记录之前操作过的链表节点，一个指针为正在操作的节点，一个指针保存原始链表顺序。

---

2、BM2 链表内指定区间反转

题目描述：

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(N)，空间复杂度O(1)。
给出的链表为 ：1→2→3→4→5→NULL, m=2,n=4,
返回 ：1→4→3→2→5→NULL.

代码实现：

public class BM2 {/*** @param head ListNode类* @param m    int整型* @param n    int整型* @return ListNode类*/public ListNode reverseBetween(ListNode head, int m, int n) {// write code here// 首先找到要开始翻转的节点 定义一个虚拟头节点ListNode fakeHead = new ListNode(0);fakeHead.next = head;int length = n - m + 1;// 记录需要反转的节点个数// 记录原始链表中，不需要被反转的的最后一个节点ListNode last = fakeHead, cur = head;while (m > 1) {cur = cur.next;last = last.next;m--;}// 此时的 cur 节点为需要反转的头节点 pre 为原始链表中不需要被翻转的最后一个节点// lastOne 记录被反转链表的头节点，也就是之后会成为尾节点ListNode pre = null, next = null, lastOne = cur;while (length > 0) {next = cur.next;cur.next = pre;pre = cur;cur = next;length--;}last.next = pre;lastOne.next = cur;return fakeHead.next;}
}

思路：

这道题开始有点晃到我了，但是仔细分析指针移动的原则，该记录就需要记录，细心一点。

---

3、BM3 链表中的节点每k个一组翻转

题目描述：

将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表。如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样。你不能更改节点中的值，只能更改节点本身。
给定的链表是 1→2→3→4→5：

• 对于 k=2 , 你应该返回 ：2→1→4→3→5；
• 对于 k=3 , 你应该返回 ：3→2→1→4→5；

代码实现：

public class BM3 {/*** @param head ListNode类* @param k    int整型* @return ListNode类*/public ListNode reverseKGroup(ListNode head, int k) {// write code hereListNode dummy = new ListNode(0);dummy.next = head;ListNode last = dummy;// 已经翻转的链表的最后一个节点ListNode pre = null, cur = head, next = null;// 每次找到下次要翻转的节点（如果为空就不翻转）while (cur != null) {// 判断是否需要翻转本轮次ListNode hasNext = cur;for (int i = 1; i < k; i++) {hasNext = hasNext.next;if (hasNext == null) {return dummy.next;}}ListNode lastOne = cur;for (int i = 0; i < k; i++) {next = cur.next;cur.next = pre;pre = cur;cur = next;}last.next = pre;last = lastOne;lastOne.next = next;}return dummy.next;}
}

---

4、BM4 合并两个排序的链表

题目描述：

• 输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
• 如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}。
• 0≤n≤1000，−1000≤节点值≤1000

代码实现：

public class BM4 {/*** @param list1：链表头1* @param list2：链表头2* @return 返回新的头节点*/public ListNode Merge(ListNode list1, ListNode list2) {ListNode dummy = new ListNode(0);// 采用虚拟头节点// 采用双指针遍历ListNode p1 = list1, p2 = list2, cur = dummy;while (p1 != null && p2 != null) {if (p1.val <= p2.val) {cur.next = p1;p1 = p1.next;} else {cur.next = p2;p2 = p2.next;}cur = cur.next;}if (p1 != null) {cur.next = p1;}if (p2 != null) {cur.next = p2;}return dummy.next;}
}

---

5、BM5 合并k个已排序的链表

题目描述：

• 合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。

代码实现：

public class BM5 {/*** 合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。** @param lists ：一个包含k个升序链表头节点的arrayList* @return*/public ListNode mergeKLists(ArrayList<ListNode> lists) {ListNode dummy = new ListNode(0);// 虚拟头节点// 利用一个优先级队列PriorityQueue<ListNode> queue = new PriorityQueue<>((ListNode a, ListNode b) -> {return a.val - b.val;});// 利用指针ListNode cur = dummy;// 将arrayList中的头节点全部加入到优先级队列中for (ListNode listNode : lists) {if (listNode != null) {queue.add(listNode);}}// 遍历while (!queue.isEmpty()) {ListNode poll = queue.poll();cur.next = poll;if ((poll = poll.next) != null) {queue.add(poll);}cur = cur.next;}return dummy.next;}
}

---

6、BM6 判断链表中是否有环

题目描述：

• 判断给定的链表中是否有环。如果有环则返回true，否则返回false。

代码实现：

public class BM6 {/*** 判断给定的链表中是否有环。如果有环则返回true，否则返回false。** @param head ： 链表的头节点* @return 返回真就是有环，false无环*/public boolean hasCycle(ListNode head) {if (head == null || head.next == null) {return false;}// 利用快慢指针法则ListNode fast = head, slow = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {return true;}}return false;}
}

---

7、BM7 链表中环的入口结点

题目描述：

• 给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

代码实现：

public class BM7 {public ListNode EntryNodeOfLoop(ListNode pHead) {// base caseif (pHead == null || pHead.next == null) {return null;}// 还是利用快慢指针ListNode fast = pHead, slow = pHead;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if (slow == fast) {fast = pHead;while (fast != slow) {fast = fast.next;slow = slow.next;}return slow;}}return null;}
}

---

8、BM8 链表中倒数最后k个结点

题目描述：

• 输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。
• 如果该链表长度小于k，请返回一个长度为 0 的链表。

代码实现：

public class BM8 {/*** @param pHead ListNode类* @param k     int整型* @return ListNode类*/public ListNode FindKthToTail(ListNode pHead, int k) {if (pHead == null) {return null;}// write code hereListNode dummy = new ListNode(0);dummy.next = pHead;ListNode slow = dummy, fast = dummy;while (k > 0) {fast = fast.next;k--;if (fast == null) {return null;}}while (fast != null) {fast = fast.next;slow = slow.next;}return slow;}
}

---

9、BM9 删除链表的倒数第n个节点

题目描述：

• 给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针。

代码实现：

public class BM9 {/*** @param head ListNode类* @param n    int整型* @return ListNode类*/public ListNode removeNthFromEnd(ListNode head, int n) {// write code hereListNode dummy = new ListNode(0);dummy.next = head;// 虚拟头节点ListNode pre = dummy, cur = head, fast = head;while (n > 0) {fast = fast.next;n--;}while (fast != null) {fast = fast.next;cur = cur.next;pre = pre.next;}pre.next = cur.next;return dummy.next;}
}

---

10、BM10 两个链表的第一个公共结点

描述：

• 输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。
• （注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

代码实现：

public class BM10 {/*** @param pHead1* @param pHead2* @return 返回链表1和链表2的第一个公共节点*/public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {int length1 = getLength(pHead1);int length2 = getLength(pHead2);// 获取两个链表的长度差值int n = length1 >= length2 ? length1 - length2 : length2 - length1;// 长短链表ListNode longHead = length1 >= length2 ? pHead1 : pHead2;ListNode shortHead = longHead == pHead1 ? pHead2 : pHead1;// 让长的链表先走while (n > 0) {longHead = longHead.next;n--;}while (longHead != null && shortHead != null) {if (longHead == shortHead) {return longHead;}longHead = longHead.next;shortHead = shortHead.next;}return null;}// 得到链表的长度int getLength(ListNode head) {int size = 0;while (head != null) {size++;head = head.next;}return size;}
}

---

11、BM11 链表相加(二)

题目描述：

• 假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
• 例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。

看到的第一眼没思路：

• 之后硬写，翻转后又翻转。。。。。

代码实现：

public class BM11 {/*** @param head1 ListNode类* @param head2 ListNode类* @return ListNode类*/public ListNode addInList(ListNode head1, ListNode head2) {// write code here// 翻转两个链表得到新的头节点ListNode reverseHead01 = reverse(head1);ListNode reverseHead02 = reverse(head2);// 新建链表int carry = 0, sum = 0;ListNode dummy = new ListNode(0);ListNode cur = dummy;while (reverseHead01 != null || reverseHead02 != null) {sum = 0;if (reverseHead01 != null) {sum += reverseHead01.val;reverseHead01 = reverseHead01.next;}if (reverseHead02 != null) {sum += reverseHead02.val;reverseHead01 = reverseHead02.next;}sum += carry;cur.next = new ListNode(sum % 10);cur = cur.next;carry = sum / 10;}if (carry == 1) {cur.next = new ListNode(1);}return reverse(dummy.next);}ListNode reverse(ListNode head) {ListNode pre = null, cur = head, next = null;while (cur != null) {next = cur.next;cur.next = pre;pre = cur;cur = next;}return pre;}}

---

12、BM12 单链表的排序

题目描述：

• 给定一个节点数为n的无序单链表，对其按升序排序。

思路：

• 这道题有点难，我不会，看了题解才做出来的。
• 根据题目中的要求，空间复杂度为O（N），时间复杂度为O（NlogN），很容易联想到归并排序。
• 将链表中的节点视为数组中的元素，申请一个和链表长度大小相等的数组空间，去存放链表中的元素。
• 但是这种写法甚为暴力。

代码实现：

public class BM12 {/*** @param head ListNode类 the head node* @return ListNode类*/public ListNode sortInList(ListNode head) {// write code here// 获取链表的长度，申请一个大小为链表长度的数组空间，存放链表中的所有元素int size = getSize(head);ListNode[] nodes = new ListNode[size];ListNode cur = head;for (int i = 0; i < size; i++) {nodes[i] = cur;cur = cur.next;}mergeSort(nodes, 0, size - 1);for (int i = 0; i < size - 1; i++) {nodes[i].next = nodes[i + 1];}nodes[size - 1].next = null;return nodes[0];}void mergeSort(ListNode[] arr, int start, int end) {if (start < end) {int mid = start + (end - start) / 2;mergeSort(arr, start, mid);mergeSort(arr, mid + 1, end);merge(arr, start, mid, end);}}void merge(ListNode[] arr, int left, int mid, int right) {ListNode[] help = new ListNode[right - left + 1];int index = 0;int i = left, j = mid + 1;while (i <= mid && j <= right) {if (arr[i].val <= arr[j].val) {help[index++] = arr[i++];} else {help[index++] = arr[j++];}}while (i <= mid) {help[index++] = arr[i++];}while (j <= right) {help[index++] = arr[j++];}for (index = 0; index <= right - left; index++) {arr[left + index] = help[index];}}// 获取链表的长度int getSize(ListNode head) {int size = 0;while (head != null) {size++;head = head.next;}return size;}
}

但是其实因为是链表，所以可以使用快慢指针。

• 如果要使用快慢指针的话，首先需要明白函数的递归含义。
• 函数就是返回以head为头结点的初始链表，排序后的新的链表的头节点。
• 将原始链表分为两段有序的链表，利用快慢指针，然后将两段分别有序的链表合并成一段有序的链表，并返回头节点。

代码实现：

    // 优美代码（拒绝暴力求解）// 返回以head为头节点的原始链表，排好序后的链表新的头节点public ListNode sortInListNice(ListNode head) {// write code here// base caseif (head == null || head.next == null) {return head;}// 利用快慢指针进行找到中间位置，将链表一分为二ListNode slow = head, fast = head.next;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}// 断掉（分成两段链表）ListNode rightHead = slow.next;slow.next = null;// 分别将两段链表进行排序ListNode left = sortInListNice(head);ListNode right = sortInListNice(rightHead);// 合并两个分别有序的链表return merge(left, right);}ListNode merge(ListNode left, ListNode right) {// 指针ListNode dummy = new ListNode(0);ListNode cur = dummy;while (left != null && right != null) {if (left.val <= right.val) {cur.next = left;left = left.next;} else {cur.next = right;right = right.next;}cur = cur.next;}if (left != null) {cur.next = left;}if (right != null) {cur.next = right;}return dummy.next;}

---

13、BM13 判断一个链表是否为回文结构

题目：

• 给定一个链表，请判断该链表是否为回文结构。
• 回文是指该字符串正序逆序完全一致。

思路：

• 这道题我还是不会。
• 无语，居然是用快慢指针，将链表一分为二后，翻转前半部分链表。
• 行吧，开干

代码实现：

public class BM13 {/*** @param head ListNode类 the head* @return bool布尔型*/public boolean isPail(ListNode head) {// write code here// 利用快慢指针，将链表一分为二ListNode slow = head, fast = head.next;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}// 斩断链表的联系if (fast != null) {slow = slow.next;}fast = reverse(slow);slow = head;while (slow != null && fast != null) {if (slow.val != fast.val) {return false;}fast = fast.next;slow = slow.next;}return true;}// 翻转链表，返回头节点public ListNode reverse(ListNode head) {ListNode pre = null, cur = head, next = null;while (cur != null) {next = cur.next;cur.next = pre;pre = cur;cur = next;}return pre;}
}

---

14、BM14 链表的奇偶重排

题目：

• 给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。
• 注意是节点的编号而非节点的数值。

代码实现：

public class BM14 {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** @param head ListNode类* @return ListNode类*/public ListNode oddEvenList(ListNode head) {// write code hereif (head == null || head.next == null) {return head;}//ListNode evenHead = head.next;ListNode odd = head, even = head.next;while (even != null && even.next != null) {odd.next = even.next;odd = odd.next;even.next = odd.next;even = even.next;}odd.next = evenHead;return head;}
}

---

15、BM15 删除有序链表中重复的元素-I

题目：

• 删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次。

代码实现：

public class BM15 {/*** @param head ListNode类* @return ListNode类*/public ListNode deleteDuplicates(ListNode head) {// write code hereif (head == null || head.next == null) {return head;}ListNode pre = head, cur = head.next;while (cur != null) {while (cur != null && cur.val == pre.val) {cur = cur.next;}pre.next = cur;pre = cur;}return head;}
}

---

16、BM16 删除有序链表中重复的元素-II

题目：

• 给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。

思路：

• 还是不会，所以写一下思路。
• 需要删除的是只要重复出现过的元素，采用递归去做。

代码实现：

public class BM16 {/*** @param head ListNode类* @return 返回原始链表，删除重复出现过的元素后的新的链表的头节点*/public ListNode deleteDuplicates(ListNode head) {// write code hereif (head == null) {return null;}// 如果当前链表头节点和后面一个节点元素相等if (head.next != null && head.val == head.next.val) {while (head.next != null && head.val == head.next.val) {head = head.next;}return deleteDuplicates(head.next);// 需要删除当前节点}head.next = deleteDuplicates(head.next);return head;}
}

---

总结：

写了一下链表章节的题目，对出现的十六道题目进行总结如下：

1. 反转链表重点在于指针的使用，合理使用虚拟头节点；
2. 指定区间内反转，还是指针的使用。先找到需要开始翻转链表的头节点，去这个链表中进行翻转。
3. 每K个一组进行翻转，还是指针的使用，需要记录下一组反转的起始位置，这一组反转的位置。
4. 合并两个排序数组，很简单。
5. 合并K个升序链表，需要用到优先级队列。
6. 判断链表是否有环，采用的是快慢指针。
7. 找到环形链表的入环节点，还是快慢指针，先判断有环，相遇之后，再去找到入环节点。
8. 链表的倒数最后K个结点，还是利用指针，一个先走然后再同时走。
9. 删除链表的倒数第N个节点，还是采用的是关于指针先走后走。
10. 两个链表的第一个公共节点， 先获取链表长度，让长的链表先走。
11. 链表相加，需要用的链表反转相加后再去翻转。
12. 单链表的排序，根据空间复杂度可以联想到归并排序，利用快慢指针，将一个链表分为两个有序的链表，然后合并两个有序的链表。
13. 判断链表是否为回文结构，用的也是快慢指针，将链表的后半部分进行翻转后，再去判断是否为回文结构。
14. 奇偶重排，还是利用指针；
15. 删除有序链表的重复元素，使得链表中所有的元素都只出现一次，指针。
16. 删除有序链表中所有重复的元素，使得链表中保留只出现一次的元素。这个很难，采用的是递归方法做的，判断当前节点元素和下一个节点元素是否相同。