经典解法就是⽤两个指针，⼀个跑得快，⼀个跑得慢。如果不含有环，跑得快的那个指针最终会遇到 null，说明链表不含环；如果含有环，快指针最终会超慢指针⼀圈，和慢指针相遇，说明链表含有环。
代码实现(java)
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null || head.next == null) return false;
ListNode fastIndex = head;
ListNode slowIndex = head;
while(fastIndex != null && fastIndex.next != null) {
slowIndex = slowIndex.next;
fastIndex = fastIndex.next.next;
if(slowIndex == fastIndex) return true;
}
return false;
}
}
已知链表有环，返回环的起点位置
思路
ListNode detectCycle(ListNode head) {
ListNode fast, slow;
fast = slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break;
}
// 上⾯的代码类似 hasCycle 函数
slow = head;
while (slow != fast) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
找到链表的中点
思路
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
// slow 就在中间位置
return slow;
寻找链表的倒数第 k 个元素
思路
代码实现
ListNode slow, fast;
slow = fast = head;
while (k-- > 0)
fast = fast.next;
while (fast != null) {
slow = slow.next;
fast = fast.next;
}
return slow;
21. 合并两个有序链表
思路
- 设立一个临时头结点dummy(设置它为不存在的节点)，让其next指向给出的链表，方便操作以及最终的返回(dummy.next)
- 在设立一个cur节点，作为链表的操作节点，指向dummy
- 循环遍历两个链表，循环条件就设为l1 != null && l2 != null
- 进入循环，每次比较 l1和l2两个节点的值的大小，找到较小的那一个进行指针的后移，与链表的链接操作
if(l1.val < l2.val) {
cur.next = l1;
cur = l1;
l1 = l1.next;
} else {
cur.next = l2;
cur = l2;
l2 = l2.next;
}
- 一直遍历知道一个链表为空，最后再判断不为空的链表，直接与结果链表相连
- 返回dummy.next就是最终的结果
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while(l1 != null && l2 != null) {
if(l1.val < l2.val) {
cur.next = l1;
cur = l1;
l1 = l1.next;
} else {
cur.next = l2;
cur = l2;
l2 = l2.next;
}
}
if(l1 == null) {
cur.next = l2;
} else {
cur.next = l1;
}
return dummy.next;
}
}
203. 移除链表元素
思路
- 设立一个临时头结点dummy(设置它为不存在的节点)，让其next指向给出的链表，方便操作以及最终的返回(dummy.next)
- 在设立一个cur节点，作为链表的操作节点，指向dummy
- 循环遍历给出链表，以cur.next作为遍历的链表元素，判断cur.next.val 是否等于 val，如果等于，就将cur.next = cur.next.next;，相当于将cur.next跳过；否则继续向后遍历cur = cur.next
- 最终返回dummy.next
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode cur = dummy;
while(cur.next != null) {
if(cur.next.val == val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return dummy.next;
}
}
206. 反转链表
思路
1 -> 2 -> 3 -> 4 -> null
null <- 1 <- 2 <- 3 <- 4
- 定义两个节点，prev = null 、cur = head 分别表示前一个节点和当前节点
- 遍历链表，每一步将当前节点的 next 指向 prev ，然后将 prev 和 cur 分别后移一位
- 以此类推，最后返回 prev 也即反转后链表的头结点
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null; // 前节点
ListNode cur = head; // 当前节点
while(cur != null) {
ListNode next = cur.next; // 临时节点，指向当前节点的后一个
cur.next = prev; // 让当前节点的next指针指向前一个节点
prev = cur; // 前节点后移到当前节点
cur = next; // 当前节点移到下一个节点
}
return prev;
}
}
83. 删除排序链表中的重复元素
思路
- 记录两个指针，pre 是指向前一个节点的指针，next是寻找后一个与 pre 不同的指针
- 遍历链表并寻找，当next.val == pre.val，说明是重复的节点，就将pre的next指针指向 next的next，然后next后移；当next.val ！= pre.val，说明不是重复节点，就将pre指向next，然后next后移
- 以此类推，最后返回head即可
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null) return head;
ListNode pre = head;
ListNode next = head.next;
while(next != null) {
if(next.val == pre.val) {
pre.next = next.next;
} else {
pre = next;
}
next = next.next;
}
return head;
}
}
