2019LeetCode暑期打卡活动 Week2 链表专题
LeetCode 19 删除链表的倒数第n个结点
做法: 找到倒数第n个节点的前一个节点
注意: 题目要求只能扫描一遍，也就是不能先得到链表长度，再找
解决: 双指针算法来做，有可能删掉头结点，虚拟头结点
步骤：
1. 建立虚拟头结点
2. 让first从虚拟头结点走n步然后停下来
3. second指向虚拟头结点，first和second同时走，first到最后一个结点时一起停下来
4. 此时second指向倒数n+1个结点
Java代码
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode first = dummy, second = dummy;
for (int i = 0; i < n; i ++ ) {
first = first.next;
}
while (first.next != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummy.next;
}
}
LeetCode 237 删除链表中的结点
做法：因为此题的输入不是头结点，是待删除的结点，所以不能通过找到前一个结点的方式来删除
注意：题目中提到，要删的结点不是尾结点
方案：让待删除的node的下一个结点伪装成node，然后，node的值为node.next的值，再删掉node.next;
Java代码
class Solution {
public void deleteNode(ListNode node) {
if (node.next == null){
node = null;
return;
}
node.val = node.next.val;
node.next = node.next.next;
}
}
LeetCode 83 删除链表中的重复结点
思路：从前往后枚举每一个点，每个点分两种情况来看
1. 如果下一个点和当前点相同，无情删掉下一个点
2. 如果下一个点和当前点不同，则指针移到下一个点
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode cur = head;
while (cur != null) {
if (cur.next != null && cur.val == cur.next.val) cur.next = cur.next.next;
else cur = cur.next;
}
return head;
}
}
LeetCode 61 旋转链表
思路
所谓的旋转是把最后一个弄到前面
旋转k次就是把后面k个移到前面
k可能很大，所以记得取模
k = 2
second first
1---2---3---4----5----[null]
(尾巴)5--->1
(倒数k+ 1)3--->null
4是新的头
3是新的尾
步骤
1. k % n
2. first从头往后走k步
3. second和first同时往后走，first走到最后一个停下来(同时走的目的是保持俩指针的差值不变)
Java代码
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null) return null;
int n = 0;
for (ListNode cur = head; cur != null; cur = cur.next) n ++ ;
k %= n;
ListNode first = head, second = head;
while (k -- > 0) first = first.next;
while (first.next != null) {
first = first.next;
second = second.next;
}
first.next = head;
head = second.next;
second.next = null;
return head;
}
}
LeetCode 24 交换相邻结点
分析：
交换相邻结点，那就每次枚举一对儿
发现头结点会发生变化，所以用虚拟头结点
p a b
dummy---1---2---3---4
b (a p)
2---1----3----4
做法
p.next = b
a.next = b.next
b.next = a
p = a
Java代码
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
for (ListNode p = dummy; p.next != null && p.next.next != null;) {
ListNode a = p.next;
ListNode b = a.next;
p.next = b;
a.next = b.next;
b.next = a;
p = a;
}
return dummy.next;
}
}
LeetCode 206 反转链表
Java代码
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) return null;
ListNode cur = head;
ListNode prev = null;
while (cur != null) {
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}
}
递归做法
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode cur = reverseList(head.next);
head.next.next = head;
head.next = null;
return cur;
}
}
LeetCode 92 反转链表2
思路
a l(b) r(c) d
dummy----1----2----3--->4--->5--->6-----7
反转[l, r]之间后
a.next = c
b.next = d
Java代码
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
if (left == right) return head;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode a = dummy, c = dummy;
for (int i = 0; i < left - 1; i ++ ) a = a.next;
for (int i = 0; i < right; i ++ ) c = c.next;
ListNode b = a.next, d = c.next;
for (ListNode p = b, q = b.next; q != d;) {
ListNode next = q.next;
q.next = p;
p = q;
q = next;
}
a.next = c;
b.next = d;
return dummy.next;
}
}
LeetCode 160 相交的链表
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode A = headA;
ListNode B = headB;
while (A != B) {
if (A == null) A = headB;
else A = A.next;
if (B == null) B = headA;
else B = B.next;
}
return A;
}
}
LeetCode 142 环形链表2 环形链表入口
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) return null;
ListNode fast = head, slow = head;
while (fast != null && slow != null) {
fast = fast.next;
slow = slow.next;
if (fast != null) fast = fast.next;
else return null;
if (fast == slow) {
fast = head;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
return null;
}
}
LeetCode 148 排序链表
Java代码
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode fast = head.next, slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
ListNode mid = slow.next;
slow.next = null;
ListNode left = sortList(head);
ListNode right = sortList(mid);
return merge(left, right);
}
ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode tail = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
if (l1 != null) tail.next = l1;
if (l2 != null) tail.next = l2;
return dummy.next;
}
}
Java快排超时了
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode left = new ListNode(-1), mid = new ListNode(-1), right = new ListNode(-1);
ListNode ltail = left, mtail = mid, rtail = right;
int val = head.val;
for (ListNode p = head; p != null; p = p.next) {
if (p.val < val) {
ltail.next = p;
ltail = ltail.next;
} else if (p.val == val) {
mtail.next = p;
mtail = mtail.next;
} else {
rtail.next = p;
rtail = rtail.next;
}
}
ltail.next = mtail.next = rtail.next = null;
left.next = sortList(left.next);
right.next = sortList(right.next);
getTail(left).next = mid.next;
getTail(left).next = right.next;
return left.next;
}
ListNode getTail(ListNode head) {
while (head.next != null) head = head.next;
return head;
}
}
