public ListNode deleteDuplicates(ListNode head) {
ListNode p = head;
while (p != null) {
// 全部删除完再移动到下一个元素
while (p.next != null && p.val == p.next.val) {
p.next = p.next.next;
}
p = p.next;
}
return head;
}
删除排序链表中的重复元素 II
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现的数字。
思路：链表头结点可能被删除，所以用 dummy node 辅助删除
public ListNode deleteDuplicates(ListNode head) {
if (head == null) {
return null;
}
ListNode newHead = new ListNode(-1, head);
ListNode p = newHead;
int n = 0;
while (p.next != null && p.next.next != null) {
if (p.next.val == p.next.next.val) {
// 记录已经删除的值，用于后续节点判断
n = p.next.val;
while (p.next != null && p.next.val == n) {
p.next = p.next.next;
}
} else {
p = p.next;
}
}
return newHead.next;
}
注意点
A->B->C 删除 B，A.next = C
删除用一个 Dummy Node 节点辅助（允许头节点可变）
访问 X.next 、X.value 一定要保证 X != nil
链表反转
反转链表
反转一个单链表。
思路：用一个 prev 节点保存向前指针，temp 保存向后的临时指针
public ListNode reverseList(ListNode head) {
ListNode pre = null, p = head;
while (p != null) {
// 保存当前head.Next节点，防止重新赋值后被覆盖
// 一轮之后状态：nil<-1 2->3->4
// prev p
ListNode temp = p.next;
p.next = pre;
// pre 移动
pre = p;
// p 移动
p = temp;
}
return pre;
}
反转链表 II
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
思路：先遍历到 m 处，翻转，再拼接后续，注意指针处理
public ListNode reverseBetween(ListNode head, int m, int n) {
// 思路：先遍历到m处，翻转，再拼接后续，注意指针处理
// 输入: 1->2->3->4->5->null, m = 2, n = 4
ListNode newHead = new ListNode(0, head);
ListNode p = newHead;
// 最开始：0(p)->1->2->3->4->5->null
for (int i = 0; i < m-1; i++) {
p = p.next;
}
// 遍历之后： 0->1(p)->2(cur)->3->4->5->null
ListNode pre = null;
ListNode cur = p.next;
for (int i = m; i <= n; i++) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
// 循环结束：0->1(p)->2->null 5(cur)->null 4(pre)->3->2->null
p.next.next = cur;
p.next = pre;
return newHead.next;
}
链表合并
合并两个有序链表
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路：通过 dummy node 链表，连接各个元素
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head = new ListNode(0);
ListNode p = head;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
p.next = l1;
l1 = l1.next;
} else {
p.next = l2;
l2 = l2.next;
}
p = p.next;
}
// 连接未处理完节点
p.next = l1 == null ? l2 : l1;
return head.next;
}
合并K个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
思路：使用分治的方法两个两个地合并链表
public ListNode mergeKLists(ListNode[] lists) {
return merge(lists, 0, lists.length - 1);
}
public ListNode merge(ListNode[] lists, int begin, int end) {
if (begin == end) return lists[begin];
if (begin > end) return null;
int mid = (begin + end) >> 1;
return mergeTwoLists(merge(lists, begin, mid), merge(lists, mid + 1, end));
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 同上
}
