LeetCode刷题笔记——HOT100面试题（2）

算法
,

双指针操作链表

19. 删除链表的倒数第N个节点

快慢双指针，快指针先走N步，然后两指针一起走，直到快指针到达尾节点，这样慢指针下一位就是要删除的结点。需要先建立一个哑节点保存链表头部，以及防止链表只有1个节点导致空指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode pHead = new ListNode(-1);
        pHead.next = head;
        ListNode pFast = pHead;
        ListNode pSlow = pHead;
        while (n>0) {
            pFast = pFast.next;
            n--;
        }
        while (pFast.next!=null) {
            pFast = pFast.next;
            pSlow = pSlow.next;
        }
        pSlow.next = pSlow.next.next;
        return pHead.next;
    }
}

141. 环形链表

快慢双指针，快指针每次走2步，慢指针每次走1步，如果存在环，则两指针必定相遇。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean hasCycle(ListNode head) {
        if (head==null) return false;
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast!=null && fast.next!=null) {
            if (fast==slow) return true;
            fast = fast.next.next;
            slow = slow.next;
        }
        return false;
    }
}

142. 环形链表II

参考《剑指Offer》链表中环的入口结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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 = head;
        while (fast!=slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

160. 相交链表

参考《剑指Offer》两个链表的第一个公共结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
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;
    }
}

合并链表

2. 两数相加

链表模拟加法，需要记录进位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode ptr = dummy;
        int carry = 0;
        while (l1!=null || l2!=null) {
            int num1 = l1==null? 0: l1.val;
            int num2 = l2==null? 0: l2.val;
            int sum = num1+num2+carry;
            ptr.next = new ListNode(sum%10);
            carry = sum/10;
            ptr = ptr.next;
            if (l1!=null) l1 = l1.next;
            if (l2!=null) l2 = l2.next;
        }
        if (carry==1) ptr.next = new ListNode(1);
        return dummy.next;
    }
}

21. 合并两个有序链表

参考归并排序的merge部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(-1);
        ListNode ptr = head;
        while (l1!=null && l2!=null) {
            if (l1.val<=l2.val) {
                ptr.next = l1;
                l1 = l1.next;
            } else {
                ptr.next = l2;
                l2 = l2.next;
            }
            ptr = ptr.next;
        }
        if (l1==null) ptr.next=l2;
        if (l2==null) ptr.next=l1;
        return head.next;
    }
}

23. 合并K个升序链表

归并排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length==0) return null;
        return mergeKLists(lists, 0, lists.length-1);
    }

    public ListNode mergeKLists(ListNode[] lists, int l, int r) {
        if (l==r) return lists[l];
        int m = l+(r-l)/2;
        ListNode l1 = mergeKLists(lists, l, m);
        ListNode l2 = mergeKLists(lists, m+1, r);
        return merge(l1, l2);
    }

    public ListNode merge(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(-1);
        ListNode ptr = head;
        while (l1!=null && l2!=null) {
            if (l1.val<=l2.val) {
                ptr.next = l1;
                l1 = l1.next;
            } else {
                ptr.next = l2;
                l2 = l2.next;
            }
            ptr = ptr.next;
        }
        if (l1==null) ptr.next = l2;
        if (l2==null) ptr.next = l1;
        return head.next;
    }
}

148. 排序链表

归并排序，先用快慢双指针把链表从中间断开，再使用合并排序链表的方式合并链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode fast = head.next;
        ListNode 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); 
    }

    public ListNode merge(ListNode left, ListNode right) {
        ListNode head = new ListNode(-1);
        ListNode ptr = head;
        while (left != null && right != null) {
            if (left.val <= right.val) {
                ptr.next = left;
                left = left.next;
            } else {
                ptr.next = right;
                right = right.next;
            }
            ptr = ptr.next;
        }
        if (left == null) ptr.next = right;
        if (right == null) ptr.next = left;
        return head.next;
    }
}

反转链表

206. 反转链表

参考《剑指Offer》反转链表。

1
2
3
4
5
6
7
8
9
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head==null || head.next==null) return head;
        ListNode next = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return next;
    }
}

234. 回文链表

用快慢双指针找到链表中点并断开链表，反转其中一段链表，比较两段链表是否相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head==null || head.next==null) return true;
        ListNode slow = head;
        ListNode fast = head.next;
        // 找到链表中点
        while (fast!=null && fast.next!=null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = slow.next;
        slow.next = null;
        mid = reverseNode(mid);
        // 逐个比较两个链表节点
        while (mid!=null) {
            if (mid.val != head.val) return false;
            mid = mid.next;
            head = head.next;
        }
        return true;
    }

    // 反转链表
    public ListNode reverseNode(ListNode head) {
        ListNode prev = null;
        while (head!=null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }  
}