# 链表：指针操作有点乱？这些技巧要记好！
# 链表不难，但是容易乱
当我们遇到链表类型的面试题时，一般都不会太难。但是很容易写错，因为经常容易搞错链表的指向关系，并且忽略对边界的处理。本节我们就以常见的链表题给大家演示几个常用的小技巧，当遇到比较复杂的题目时，还可以画图辅助梳理链表的指向关系
- 假头
- 新链表
- 双指针
- 拆分成多个链表再合并
后面演示用到的链表类定义如下
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val; this.next = next;
}
}
# 假头和新链表
链表有些题目还是需要如果想追求高性能，还是会用到一些稍微复杂的算法。但如果你在笔试阶段实在想不到更高效的算法。就直接重新构造一个新链表返回，但是时间复杂度和空间复杂度会比较高。如将链表排序，合并N个有序链表
# 排序链表
题目来源：LeetCode 148
给你链表的头结点 head ，请将其按升序排列并返回排序后的链表 。
我们直接遍历这个链表，将值存下来，然后重新构建
public ListNode sortList(ListNode head) {
if (head == null) {
return null;
}
List<Integer> resultList = new ArrayList<>();
while (head != null) {
resultList.add(head.val);
head = head.next;
}
Collections.sort(resultList);
// 构建链表
ListNode tempHead = null, newHead = null;
for (int i = 0; i < resultList.size(); i++) {
if (i == 0) {
newHead = new ListNode(resultList.get(i));
tempHead = newHead;
} else {
ListNode listNode = new ListNode(resultList.get(i));
newHead.next = listNode;
newHead = newHead.next;
}
}
return tempHead;
}
可以看到，我们要对头节点的操作进行特判，还是比较麻烦的。此时我们可以构建一个假头（命名为dummy），放在要返回的头节点的前面，这样当我们对链表进行增加，删除等操作时，就非常方便
public ListNode sortList(ListNode head) {
if (head == null) {
return null;
}
List<Integer> resultList = new ArrayList<>();
while (head != null) {
resultList.add(head.val);
head = head.next;
}
Collections.sort(resultList);
ListNode dummy = new ListNode();
ListNode dummyTemp = dummy;
for (Integer item : resultList) {
ListNode listNode = new ListNode(item);
dummy.next = listNode;
dummy = dummy.next;
}
return dummyTemp.next;
}
# 反转链表
题目来源：LeetCode 206
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
如果我们基于原来的链表进行操作还是比较麻烦的。如果换一种思路，重新构建一个新链表然后返回，实现过程是不是一下就清晰起来了？
遍历旧的链表，然后将旧链表的节点不断设置为新链表的头节点，最后返回的新链表就是反转后的。为了简化操作过程，我们还是弄一个假头
public ListNode reverseList(ListNode head) {
ListNode dummy = new ListNode();
while (head != null) {
ListNode curNode = head;
head = head.next;
// 下面2行代码为将旧链表的节点设置为新链表的头节点
curNode.next = dummy.next;
dummy.next = curNode;
}
return dummy.next;
}
# 双指针
链表中的双指针操作一般有两种，一种是比较常规的用法，如用2个指针记录2个链表的移动过程。另一种是快慢指针，能实现很多有意思的操作。
# 合并2个有序链表
题目来源：LeetCode 21
我们使用双指针，标记2个链表的移动，然后构建新链表
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode dummy = new ListNode();
ListNode tempDummy = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
dummy.next = l1;
l1 = l1.next;
} else {
dummy.next = l2;
l2 = l2.next;
}
dummy = dummy.next;
}
// l1链表遍历完了，把l2剩余的节点加上去
if (l1 == null) {
dummy.next = l2;
}
// l2链表遍历完了，把l1剩余的节点加上去
if (l2 == null) {
dummy.next = l1;
}
return tempDummy.next;
}
# 删除链表的倒数第n个节点
题目来源：LeetCode 19
大部分人都能很快想到解法，先遍历一遍得到链表的长度，再遍历一遍删除节点。
有没有可能通过一次遍历就做到呢？
用快慢2个指针即可做到，快指针先走n步，然后快慢指针一起走。当快指针到达链表的尾部时，慢指针正好是倒数第n+1个节点，重新设置倒数第n+1个节点的next指针即可
链表长度是是n，删除倒数第n个节点这种情况怎么处理呢？
上面说到，我们先找倒数第n+1个节点，然后重新设置next指针。但是当链表长度为n时，倒数第n+1个节点不存在，为了保持逻辑的统一性，我们只需要加一个假头即可，和前面的反转链表一个道理，这样处理起来比较容易，代码也比较容易理解
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
ListNode slow = dummy;
ListNode fast = dummy;
for (int i = 0; i <= n; i++) {
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
# 判断链表是否是回文链表
当一个链表正着读和反着读都一样时，则这个链表是回文链表，否则不是回文链表。
我们同样可以用快慢指针来解决这种类型的题目。慢指针每次走1步，快指针每次都2步。当快指针到头的时候，慢指针正好在链表的中点。
此时同时移动链表的头节点指针和慢节点指针，当2者的值不同时，说明这个链表不是回文链表
public boolean isPalindrome(ListNode head) {
ListNode pre = new ListNode();
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
ListNode node = new ListNode(slow.val, pre.next);
pre.next = node;
slow = slow.next;
fast = fast.next.next;
}
if (fast != null) {
slow = slow.next;
}
pre = pre.next;
while (slow != null) {
if (slow.val != pre.val) {
return false;
}
slow = slow.next;
pre = pre.next;
}
return true;
}
# 判断链表是否有环
题目来源：LeetCode 141
如上图链表，-4节点到2节点就形成了一个环
我们只需要把访问过的节点都记录下来，每次访问一个节点就判断这个节点是否被访问过即可。
记录这个节点是否访问的方法有很多种
- 给ListNode增加一个属性visit，默认为false，访问过则置为true，将新访问到的ListNode的visit为true时，说明链表有环
- 用HashMap存储访问过的ListNode，注意不要重写hashCode和equals，这样只有同一个对象才能被判断为相等，当新访问到的ListNode在HashMap中存在时，说明链表有环
- 将访问过的ListNode放到Set中（相同的ListNode会自动去重哈），如果将新访问的ListNode放入Set中，set的数量没有增加，说明链表有环
public boolean hasCycle(ListNode head) {
Map<ListNode, Boolean> listNodeMap = new HashMap();
while (head != null) {
if (listNodeMap.containsKey(head)) {
return true;
}
listNodeMap.put(head, null);
head = head.next;
}
return false;
}
当然最高效的方式还使用快慢指针，快指针每次走一步，慢指针每次走两步，如果链表有环，则快慢指针迟早会相遇。
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast!= null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
return true;
}
}
return false;
}
# 拆分成多个链表再合并
# 链表的奇偶重排
题目描述：
题目来源：BM14（牛客网）
思路：直接基于原链表移动比较复杂，直接新建2个链表，一个插入链表的奇数位节点，一个插入链表的偶数位节点，最后将这2个链表合并起来即可
public class Solution {
public ListNode oddEvenList (ListNode head) {
if (head == null) {
return null;
}
ListNode oddHead = new ListNode(0);
ListNode oddTail = oddHead;
ListNode evenHead = new ListNode(0);
ListNode evenTail = evenHead;
for (int i = 1; head != null; i++) {
if ((i & 1) == 1) {
oddTail.next = head;
oddTail = head;
} else {
evenTail.next = head;
evenTail = head;
}
head = head.next;
}
evenTail.next = null;
oddTail.next = evenHead.next;
return oddHead.next;
}
}