1. 删除链表中等于给定值 val 的所有节点。
技巧：先删除后面的节点，最后处理头结点
如果先删除头结点，新的头结点也可能是待删除的元素，处理起来就麻烦一些，删除节点的时候，需要先找到待删除节点的前一个节点，反正都是需要遍历链表，就可以遍历的过程中把前一个节点记住就好了
class Solution {
public ListNode removeElements(ListNode head, int val) {
if (head == null) {
return null;
}
// 删除操作是需要找到当前节点的前一个节点的
ListNode prev = head; //待删除的节点的前一个节点
ListNode cur = head.next; //待删除节点
while (cur != null) {
if (cur.val == val) {
// 如果找到了值为 val 的节点
// 就需要删除这个节点
prev.next = cur.next;
cur = prev.next;
} else {
// 如果没找到，更新 prev 和 cur 的位置
prev = prev.next;
cur = cur.next;
}
}
// 删除操作也需要单独考虑待删除元素是头结点的情况
if (head.val == val) {
head = head.next;
}
return head;
}
}
2.反转一个单链表。
三指针/引用法
使用prev记录前一个节点
使用cur记录当前节点
使用next记录下一个节点
核心操作：cur.next = prev
原链表的最后一个节点，就成了新链表的头结点，记得把这个新的头结点给返回回去
class Solution {
public ListNode reverseList(ListNode head) {
// 写任意代码的时候，都要记得把特殊情况都处理到位
if (head == null) {
return null;
}
if (head.next == null) {
// 链表里只有一个节点
return head;
}
// 处理一般情况
ListNode newHead = null;
ListNode prevNode = null;
ListNode curNode = head;
ListNode nextNode = curNode.next;
while (curNode != null) {
// 进入循环的时候，需要先设定好 nextNode 的位置
nextNode = curNode.next;
if (nextNode == null) {
// curNode 就指向了最后一个节点
// 也就是反转后新链表的头结点
newHead = curNode;
}
// 掰道岔
curNode.next = prevNode;
// 更新引用的位置
prevNode = curNode;
curNode = nextNode;
}
return newHead;
}
}
3. 给定一个头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
实现思路：
1.先求出链表的总长度
2.根据总长度 / 2，让一个引用从头开始走这些步数即可
class Solution {
public int getLength(ListNode head) {
// 遍历链表即可
int length = 0;
for (ListNode cur = head; cur != null; cur = cur.next) {
length++;
}
return length;
}
public ListNode middleNode(ListNode head) {
// 虽然题目要求说 head 是一个非空单链表
// 但是题目的实际测试用例，可能会有空链表
// 实际面试的时候，面试官一般还是希望能写出合法性校验的代码的（良好的编程意识）
if (head == null) {
return null;
}
// 求链表的长度
int length = getLength(head);
// 针对长度 / 2, 得到的是引用走的步数
int steps = length / 2;
// 控制引用往后走
ListNode cur = head;
for (int i = 0; i < steps; i++) {
cur = cur.next;
}
return cur;
}
}
4. 输入一个链表，输出该链表中倒数第k个结点。
1 2 3 4 5
长度是len，k最多取值就是len
链表是单链表，不能从后往前走，还是得从前往后走
要想得到倒数第1个节点，就从头开始走4步
要想得到倒数第2个节点，就从头开始走3步
要想得到倒数第k个节点，就从头开始走len - k步
代码：
public class Solution {
public int getLength(ListNode head) {
// 遍历链表即可
int length = 0;
for (ListNode cur = head; cur != null; cur = cur.next) {
length++;
}
return length;
}
public ListNode FindKthToTail(ListNode head,int k) {
if (head == null) {
return null;
}
if (k <= 0) {
return null;
}
int length = getLength(head);
if (k > length) {
// k 允许等于 length
return null;
}
// 得到倒数第 k 个节点，就让引用从头开始，走 length - k
int steps = length - k;
ListNode cur = head;
for (int i = 0; i < steps; i++) {
cur = cur.next;
}
// 此时，cur 就指向了倒数第 k 个节点
return cur;
}
}
5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
实现思路：
1）先创建两个引用分别指向两个链表的第一个节点，比较这两个引用指向的节点值的大小
2）把较小的节点，插入到结果链表的末尾
3）该节点得插入到新链表后，对应的引用也要移动到next的位置上
4）循环刚才的比较和插入过程，直到两个引用其中的某一个到达null（链表末尾）
5）到达链表末尾之后，就把另一个非空的链表剩余的尾巴都统一插入到结果链表的末尾
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
// 两个链表都为空，进行合并
ListNode cur1 = l1;
ListNode cur2 = l2;
// 为了简化后续的插入操作，此处使用一个 带傀儡节点 的链表
ListNode newHead = new ListNode(0); // 创建了一个新的链表，用来保存最终结果
// 后续需要频繁进行尾插，为了尾插方便，使用一个变量把链表的尾部都给记录下来
// 链表一般都是用头结点来表示，但是也是完全可以通过其他引用记录其他位置，典型的就是记录尾结点
ListNode newTail = newHead;
// 进行循环遍历两个链表，并比较 任意循环到达链表末尾，都算循环结束
while (cur1 != null && cur2 != null) {
if (cur1.val < cur2.val) {
// 就把cur1 插入到新链表末尾
newTail.next = cur1;
cur1 = cur1.next;
} else {
// 就把cur2 插入到新链表末尾
newTail.next = cur2;
cur2 = cur2.next;
}
newTail = newTail.next;
}
// 当上述循环结束，意味着一定有一个引用已经到达了链表末尾
// 于是就把另一个链表的剩余部分插入过来即可
if (cur1 == null) {
newTail.next = cur2;
} else {
newTail.next = cur1;
}
// 返回结果链表
return newHead.next;
}
}
6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
实现思路：
1）遍历链表，判断每个节点的值和x的大小关系
2）如果比x小，把这个节点插入到一个smallList中
3）如果比x大于等于，就把这个节点插入到一个largeList中
4）最终把smallList和LargeList给拼接起来就行了
public class Partition {
public ListNode partition(ListNode pHead, int x) {
if (pHead == null) {
return null;
}
if (pHead.next == null) {
return pHead;
}
// 处理一般情况。需要创建两个链表，用来保存两部分结果
// 为了方便后续的尾插操作，仍然使用带傀儡节点的链表，同时记录链表的末尾
ListNode smallHead = new ListNode(0);
ListNode smallTail = smallHead;
ListNode largeHead = new ListNode(0);
ListNode largeTail = largeHead;
for (ListNode cur = pHead; cur != null; cur = cur.next) {
if (cur.val < x) {
// 比基准值小，就插入到 smallHead 的末尾
// 由于旧的链表是使用 for 的方式直接遍历，就会一直执行到 cur = cur.next
// 通过这样的方式尾插，可能会对原来链表的遍历造成影响，稳妥起见，创建新的节点，而不是拆掉旧的链表
smallTail.next = new ListNode(cur.val);
smallTail = smallTail.next;
} else {
// 大于等于基准值，就插入到 largeHead 的末尾
largeTail.next = new ListNode(cur.val);
largeTail = largeTail.next;
}
}
// 经过了上面的循环，此时链表已经被拆成两个部分了
// 第一部分就是都小于 x 的元素
// 第二部分就都是大于等于 x 的元素
// 最后一步，需要把两个链表合成一个，直接收尾相接即可
smallTail.next = largeHead.next;
return smallHead.next;
}
}
7.在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
实现思路：
1） 遍历列表，需要找到哪些节点是重复节点
2）排序链表中的重复节点一定是相邻的
3）如果当前节点是重复节点，直接跳过下一个，如果当前节点不是重复节点，就把这个节点给插入到新链表中
4）cur . val == cur . next . val 如果这样的条件成立，就说明cur和cur .next就是重复节点
注意：重复节点不一定只重复一次
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
if (pHead == null) {
return null;
}
if (pHead.next == null) {
// 链表只有一个节点
return pHead;
}
// 用来保存节点的链表,该链表也是一个带傀儡节点的链表
// 为了尾插方便，记录链表的尾部
ListNode newHead = new ListNode(0);
ListNode newTail = newHead;
// 遍历链表，判定其中是否存在重复的节点
ListNode cur = pHead;
while (cur != null) {
if (cur.next != null && cur.val == cur.next.val) {
// 发现cur是重复节点,就需要找到接下来不重复的节点
while (cur != null && cur.next != null && cur.val == cur.next.val) {
cur = cur.next;
}
// 上面的循环结束，要么是 cur 已经到达了末尾，要么是 cur 已经遇到了不重复的节点
// 此时需要让 cur 再往后走一步，直接插入到 newHead 末尾即可
} else {
// cur不是重复节点，直接插入到 newHead 末尾即可
newTail.next = new ListNode(cur.val);
newTail = newTail.next;
}
// 循环需要往下走一步
cur = cur.next;
}
return newHead.next;
}
}
8. 链表的回文结构。
实现思路：
1）如果是数组的话，搞一个下标left，从0开始；搞一个下标right，从 length - 1开始；判定arr[right]和arr[left]是否相等，如果相等，left++，right–，直到left和right重合。
2）单链表逆置
a）给定一个链表A，先把这个链表A拷贝一份，得到B
b）把B逆置
c）对比A和B是不是一样的链表就搞定了
public class PalindromeList {
public boolean chkPalindrome(ListNode A) {
if (A == null) {
// 空链表，直接返回数组
return true;
}
if (A.next == null) {
return true;
}
// 1. 把原来的链表复制一份
ListNode newHead= new ListNode(0);
ListNode newTail = newHead;
for (ListNode cur = A; cur != null; cur = cur.next) {
newTail.next = new ListNode(cur.val);
newTail = newTail.next;
}
ListNode B = newHead.next;
// 2. 把新链表逆置
ListNode prev = null;
ListNode cur = B;
while (cur != null) {
ListNode next = cur.next;
if (next == null) {
// cur 就指向最后一个节点了，也就是逆置后链表的头结点
B = cur;
}
// 逆置的核心操作：掰道岔
cur.next = prev;
// 更新循环变量
prev = cur;
cur = next;
}
// 3. 对比两个链表是否一样
ListNode cur1 = A;
ListNode cur2 = B;
while (cur1 != null && cur2 != null) {
if (cur1.val != cur2.val) {
// 找到了反例，不是回文
return false;
}
cur1 = cur1.next;
cur2 = cur2.next;
}
// 找了一圈下来也没找到反例，于是就判定这是回文
return true;
}
}
9. 输入两个链表，找出它们的第一个公共结点。（判断链表相交）
实现思路：
1）分别求出两个链表的长度 l1，l2
2）分别创建两个引用，指向两个链表的头结点 cur1，cur2
3）看看这两链表谁长，假设是l1 > l2， 就让cur1先走l1 - l2步；如果l1 < l2，就让cur2先走l2 - l1 步
4）此时让cur1和cur2同时以相同的速度往后走，看是否相遇。当cur1和cur2 相遇的时候，此时这个位置正是链表的交点
public class Solution {
public int getLength(ListNode head) {
int length = 0;
for (ListNode cur = head; cur != null; cur = cur.next) {
length++;
}
return length;
}
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// 1. 求两个链表的长度
int len1 = getLength(headA);
int len2 = getLength(headB);
// 2. 让长的链表先走
if (len1 > len2) {
int steps = len1 - len2;
for (int i = 0; i < steps; i++) {
headA = headA.next;
}
} else {
int steps = len2 - len1;
for (int i = 0; i < steps; i++) {
headB = headB.next;
}
}
// 3. 此时 headA 和 headB 已经在同一起跑线了，于是就同步往后走，看能否相遇
while (headA != null && headB != null) {
// 此处比较的不是节点里的 val， 而是节点对象的身份
if (headA == headB) {
// 相交了，交点也找到了
return headA;
}
headA = headA.next;
headB = headB.next;
}
return null;
}
}
10. 给定一个链表，判断链表中是否有环。
实现思路：链表上某个节点的next，指到了前面的某个节点
快慢指针：创建两个引用fast，slow，fast每走两步，slow每走一步。如果链表不带环，此时fast就会率先到达终点null；如果链表带环，fast和slow进入环中之后，fast就会把slow给套圈
public class Solution {
public boolean hasCycle(ListNode head) {
// 快慢指针
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
return true;
}
}
return false;
}
}
11. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null
实现思路：
求出环的入口点
public class Solution {
public ListNode detectCycle(ListNode head) {
// 快慢指针，先找到快慢指针重合的位置
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
break;
}
}
if (fast == null || fast.next == null) {
// 说明链表是不带环的
return null;
}
// 如果带环，从链表头 和 fast slow 交汇的位置同时出发，两个引用相遇位置就是环的入口
ListNode cur1 = head;
ListNode cur2 = fast;
while (cur1 != cur2) {
// 在解引用之前，比如 cur1.next 之前要保证 cur1 是非空的
// 当前链表已经是带环了，带环的链表上没有 null
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}
}