1. 两个链表第一个公共子节点
LeetCode160
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
listA = [4,1,8,4,5], listB = [5,6,1,8,4,5]
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构
1.1. 集合
/**
* 方法1：通过集合来辅助查找
*
* @param headA
* @param headB
* @return
*/
public static ListNode findFirstCommonNodeBySet(ListNode headA, ListNode headB) {
HashSet<ListNode> set = new HashSet<>();
// 将第一个链表的每个节点放入set中
while (headA != null) {
set.add(headA);
headA = headA.next;
}
// 遍历第二个链表中的每个节点，判断是否存在于set中
while (headB != null) {
if (set.contains(headB))
return headB;
headB = headB.next;
}
return null;
}1.2. 哈希
/**
* 方法2：通过Hash辅助查找
*
* @param pHead1
* @param pHead2
* @return
*/
public static ListNode findFirstCommonNodeByMap(ListNode pHead1, ListNode pHead2) {
// 两个链表的头结点不能为空
if (pHead1 == null || pHead2 == null) {
return null;
}
ListNode current1 = pHead1;
ListNode current2 = pHead2;
HashMap<ListNode, Integer> hashMap = new HashMap<>();
// 将第一个链表中的每个节点存入 hashmap，没有用到hashmap的value，只用到了key，所以本题使用hashset结构更合适
while (current1 != null) {
hashMap.put(current1,null);
current1 = current1.next;
}
// 遍历第二个链表，判断key是否存在hashmap中
while (current2 != null) {
if (hashMap.containsKey(current2)) {
return current2;
}
current2 = current2.next;
}
return null;
}1.3. 栈
/**
* 方法3：通过栈
*/
public static ListNode findFirstCommonNodeByStack(ListNode headA, ListNode headB) {
// 定义两个栈 将两个链表的节点存放到两个栈中
Stack<ListNode> stackA = new Stack<>();
Stack<ListNode> stackB = new Stack<>();
// 将两个链表的节点存放到两个栈中
while (headA != null) {
stackA.push(headA);
headA = headA.next;
}
while (headB != null) {
stackB.push(headB);
headB = headB.next;
}
// 比较两个栈 栈顶的值 若相等则出栈，直至找到最后一组相等的结点
ListNode pNode = null;
while (stackA.size() > 0 && stackB.size() > 0) {
if (stackA.peek() == stackB.peek()) {
pNode = stackA.pop();
stackB.pop();
}else {
break;
}
}
return pNode;
}2. 回文串
LeetCode234
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1] 输出：true
示例 2：
输入：head = [1,2] 输出：false
2.1. 全部压栈
/**
* 方法2：全部压栈
*
* @param head
* @return
*/
public static boolean isPalindromeByAllStack(ListNode head) {
// 定义栈 将链表中结点的值依次压入栈
Stack<Integer> stack = new Stack<>();
ListNode temp = head;
while (temp != null) {
stack.push(temp.val);
temp = temp.next;
}
// 栈中的值依次出栈，与链表中的值依次比较，若有一个不一致，则不是回文串
// 栈中的值出栈顺序为原顺序逆序，head从头遍历，正好符合回文串定义
while (head != null) {
if (head.val != stack.pop()){
return false;
}
head = head.next;
}
return true;
}2.2. 将所有数据压栈，仅弹出一半数据进行比较
/**
* 方法3：将所有数据压栈，仅弹出一半数据进行比较
* 因为回文串，前半部分的逆序就是后半部分，所以只需比较一半数据即可
* @param head
* @return
*/
public static boolean isPalindromeByHalfStack(ListNode head) {
if (head == null)
return true;
ListNode temp = head;
Stack<Integer> stack = new Stack<>();
//链表的长度
int len = 0;
//把链表节点的值存放到栈中
while (temp != null) {
stack.push(temp.val);
temp = temp.next;
len++;
}
//len长度除以2，右移1位，左边加0，相当于除以2
len >>= 1;
//然后再出栈
while (len-- >= 0) {
if (head.val != stack.pop())
return false;
head = head.next;
}
return true;
}3. 合并有序链表
3.1. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：L1 = [1,2,4], L2 = [1,3,4] 输出：[1,1,2,3,4,4]
示例 2：
输入：L1 = [], L2 = [] 输出：[]
示例 3：
输入：L1 = [], L2 = [0] 输出：[0]
3.1.1. 基本思路
新建一个链表，然后分别遍历两个链表，每次都选择最小的结点连接到新链表上。
/**
* 方法1：最基础的做法
* 新建一个链表，然后分别遍历两个链表，每次都选择最小的结点连接到新链表上。
* @param list1
* @param list2
* @return
*/
public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// 新建一个链表，这个新链表有一个虚拟头结点，便于处理
ListNode newNode = new ListNode(-1);
// 因为newNode需要移动，所以先赋值给res备份一下
ListNode res = newNode;
while (list1 != null || list2 != null) {
if (list1 != null && list2 != null) {
// 如果第一个链表的值大于第二个链表的值，则将第二个链表的值加到新链表newNode上
if (list1.val > list2.val) {
newNode.next = list2;
list2 = list2.next;// 将list2的头指针往后移动一个位置
} else if (list1.val < list2.val) {
newNode.next = list1;
list1 = list1.next;
} else {
newNode.next = list2;
list2 = list2.next;
newNode = newNode.next;
newNode.next = list1;
list1 = list1.next;
}
newNode = newNode.next; // 将newNode的头指针往后移动一个位置
}
if (list1 != null && list2 == null) { // 此时list2已经为空，只需连接list1的值
newNode.next = list1;
list1 = list1.next;
newNode = newNode.next;
}
if (list1 == null && list2 != null) {
newNode.next = list2;
list2 = list2.next;
newNode = newNode.next;
}
}
return res.next;
} /**
* 方法2：比方法1更加精简的实现方法
*
* @param l1
* @param l2
* @return
*/
public static ListNode mergeTwoListsMoreSimple(ListNode l1, ListNode l2) {
ListNode prehead = new ListNode(-1);
ListNode prev = prehead;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
// 最多只有一个还未被合并完，直接接上去就行了,这是链表合并比数组合并方便的地方
prev.next = l1 == null ? l2 : l1;
return prehead.next;
}3.2. 合并K个链表
/**
* 合并K个链表
*
* @param lists
* @return
*/
public static ListNode mergeKLists(ListNode[] lists) {
ListNode res = null;
for (ListNode list : lists) {
res = mergeTwoListsMoreSimple(res, list);
}
return res;
}3.3. 合并两个链表
LeetCode1669
给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。
请你将 list1 中下标从 a 到 b 的全部节点都删除，并将list2 接在被删除节点的位置。
下图中蓝色边和节点展示了操作后的结果：
请你返回结果链表的头指针。
示例 ：
输入：list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002] 输出：[0,1,2,1000000,1000001,1000002,5] 解释：我们删除 list1 中下标为 3 和 4 的两个节点，并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。
思路：找到链表list1保留部分的尾结点和链表list2的尾结点，将两链表连接起来就行了。
public static ListNode mergeInBetween(ListNode list1, ListNode list2, int a, int b) {
ListNode pre1 = list1,post1 = list1, post2 = list2;
int i = 0, j = 0;
while (pre1 != null && post1 != null && j < b + 1) {
// 找到链表1，位置a的前一个位置
if (i < a - 1) {
pre1 = pre1.next;
i++;
}
// 找到链表1，位置b的后一个位置
if (j < b + 1) {
post1 = post1.next;
j++;
}
}
// 寻找list2的尾结点
while (post2.next != null){
post2 = post2.next;
}
// 链表1尾巴连接链表2头部，链2尾部连接链1后半部分的头
pre1.next = list2;
post2.next = post1;
return list1;
}
4. 双指针
4.1. 寻找中间结点
LeetCode876
给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：head = [1,2,3,4,5] 输出：[3,4,5] 解释：链表只有一个中间结点，值为 3 。
示例 2：
输入：head = [1,2,3,4,5,6] 输出：[4,5,6] 解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。
思路：
慢指针一次移动一个结点，快指针一次移动两个结点
public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
if (head == null) {
return head;
}
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}4.2. 寻找链表的倒数第K个元素
输入一个链表，输出该链表中倒数第k个节点。本题从1开始计数，即链表的尾节点是倒数第1个节点。
示例 给定一个链表: 1->2->3->4->5, 和 k = 2。
输出： 4。
/**
* 给出k，找出该链表倒数第K个结点
* 思路：fast指针先走到第K个结点，然后fast和slow 同时走，当fast指向null的时候，slow指向倒数第K个结点
* @param head
* @param k
* @return
*/
public static ListNode getKthFromEnd(ListNode head, int k) {
ListNode fast = head;
ListNode slow = head;
// 让fast指向第K个结点
while (fast != null && k > 0){
fast = fast.next;
k--;
}
// 让fast 和 slow同步移动
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
4.3. 旋转链表
LeetCode61
给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
示例 1：
输入：head = [1,2,3,4,5], k = 2 输出：[4,5,1,2,3]
思路：
先用双指针策略找到倒数K的位置，也就是{1,2,3}和{4,5}两个序列，之后再将两个链表拼接成{4,5,1,2,3}就行了。具体思路是： 因为k有可能大于链表长度，所以首先获取一下链表长度len，如果然后k=k % len，如果k == 0，则不用旋转，直接返回头结点。否则：
- 快指针先走k步。
- 慢指针和快指针一起走。
- 快指针走到链表尾部时，慢指针所在位置刚好是要断开的地方。把快指针指向的节点连到原链表头部，慢指针指向的节点断开和下一节点的联系。
- 返回结束时慢指针指向节点的下一节点。
public ListNode rotateRight(ListNode head, int k) {
// 当K为0或者头结点为空的时候，直接返回头节点
if (k == 0 || head == null) {
return head;
}
ListNode temp = head;// 备份头结点
ListNode fast = head;
ListNode slow = head;
int len = 0;
// 拿到链表长度len
while(head != null) {
head = head.next;
len++;
}
if (k % len == 0) {
return temp;
}
// 用快指针找到倒数第K+1个节点
while((k % len) >0) {
k--;
fast = fast.next;
}
// 快慢指针同时移动，快指针移动到最后一个元素时，慢指针指向倒数第K+1个节点
while(fast.next != null) {
fast = fast.next;
slow = slow.next;
}
ListNode res = slow.next;
slow.next = null;
fast.next = temp;
return res;
}5. 删除结点
5.1. 删除特定结点
LeetCode203
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]
思路：
- 我们创建一个虚拟链表头dummyHead，使其next指向head。
- 开始循环链表寻找目标元素，注意这里是通过cur.next.val来判断的。
- 如果找到目标元素，就使用cur.next = cur.next.next;来删除。
- 注意最后返回的时候要用dummyHead.next，而不是dummyHead。
public ListNode removeElements(ListNode head, int val) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode cur = dummyHead;
while (cur.next != null) {
if (cur.next.val == val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return dummyHead.next;
}5.2. 删除倒数第n个结点
LeetCode19
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]
public static ListNode removeNthFromEndByTwoPoints(ListNode head, int n) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode fast = head;
ListNode slow = dummyHead;
for (int i = 0; i < n; ++i) {
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
assert slow.next != null;
slow.next = slow.next.next;
return dummyHead.next;
}5.3. 删除重复元素
5.3.1. 保留一个重复元素
LeetCode83
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
示例 1：
输入：head = [1,1,2] 输出：[1,2]
思路：
由于给定的链表是排好序的，因此重复的元素在链表中出现的位置是连续的，因此我们只需要对链表进行一次遍历，就可以删除重复的元素。具体地，我们从指针 cur 指向链表的头节点，随后开始对链表进行遍历。如果当前 cur 与cur.next 对应的元素相同，那么我们就将cur.next 从链表中移除；否则说明链表中已经不存在其它与cur 对应的元素相同的节点，因此可以将 cur 指向 cur.next。当遍历完整个链表之后，我们返回链表的头节点即可。 另外要注意的是 当我们遍历到链表的最后一个节点时，cur.next 为空节点，此时要加以判断。
public ListNode deleteDuplicates(ListNode head) {
if (head == null) {
return head;
}
ListNode cur = head;
while (cur.next != null) {
if (cur.val == cur.next.val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
}5.3.2. 删除所有重复元素
LeetCode82
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
示例 1：
输入：head = [1,2,3,3,4,4,5] 输出：[1,2,5]
为了防止开头就有重复的元素，这个题搞一个虚拟头结点
public ListNode deleteDuplicates(ListNode head) {
if (head == null) {
return head;
}
// 使用第三个构造函数，直接将虚拟节点连接到头结点head
ListNode dummyHead = new ListNode(0, head);
ListNode cur = dummyHead;
while (cur.next != null && cur.next.next != null) {
if (cur.next.val == cur.next.next.val) {
int x = cur.next.val;
// 实在是巧妙
while (cur.next != null && cur.next.val == x) {
cur.next = cur.next.next;
}
} else {
cur = cur.next;
}
}
return dummyHead.next;
}
