LeetCode刷题笔记——腾讯面试精选50题（2）

链表

删除链表中的节点

思路：删除链表中的某一个节点的通常方法是要删除的节点的前一节点直接指向后一节点。这里无法向前访问节点，因此将后一节点的值赋予要删除的节点，并且该节点直接指向后后一节点（等于是删除了后一节点）。

class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

反转链表

思路：设置一个哑节点作为原链表的头节点。将当前链表的next指针指向它前面的节点，然后迭代。

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}

合并两个有序链表

思路：比较两个链表的头节点，取出较小的接在合并链表节点的后面。当有一个链表已经为空时，非空的链表全部接入合并链表后面。

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

相交链表

思路：链表A和链表B如果是等长的，那么它们一起遍历一定会遇到相交点。因此考虑使其长度等长：链表A遍历到尾节点后开始遍历链表B，同时链表B遍历完成后开始遍历链表A。它们的指针一定会在相交节点相遇（除非两个链表本身就是不相交的）。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode dummyA = headA;
        ListNode dummyB = headB;
        while (headA != headB) {
            if (headA == null) headA = dummyB;
            else headA = headA.next;
            if (headB == null) headB = dummyA;
            else headB = headB.next;
        }
        return headA;
    }
}

环形链表

思路：此题使用快慢双指针法。如果链表存在环，则两个指针必定会在某一个节点相遇，否则快指针会先到达尾部。

public 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;
    }
}

排序链表

思路：题目要求时间复杂度在O(nlogn)，因此考虑使用归并排序。链表的归并排序在不使用递归的情况下可以做到常数级的空间复杂度。

1. 分割：使用快慢双指针，找到链表的中点并切断，直到分成长度为1的节点为止。然后进行合并操作。
2. 合并：设置两个头指针，分别遍历两个链表，依次将节点合并；如果有一个链表已经遍历完，将另一个链表剩余的部分接在当前节点之后。

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode pFast = head.next;
        ListNode pSlow = head;
        while (pFast != null && pFast.next != null) {
            pFast = pFast.next.next;
            pSlow = pSlow.next;
        }
        ListNode mid = pSlow.next;
        pSlow.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 curr = head;
        while (left != null && right != null) {
            if (left.val <= right.val) {
                curr.next = left;
                left = left.next;
            } else {
                curr.next = right;
                right = right.next;
            }
            curr = curr.next;
        }
        if (left == null) curr.next = right;
        if (right == null) curr.next = left;
        return head.next;
    }
}

环形链表 II

标签：链表，双指针

思路：使用快慢双指针，若快指针走到链表尾节点，则表示不存在环；若存在环则两指针必定相遇，此时快指针回到头节点并与慢指针同速度遍历，两指针会在环入口相遇。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) return head;
        ListNode fast = head, slow = head;
        do {
            if (fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
        } while (fast != slow);
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}

旋转链表

思路：与189. 旋转数组类似，使用三次翻转来解答此题。

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) return head;
        ListNode cur = head;// 计算链表长度
        int len = 0;
        while (cur != null) {
            cur = cur.next;
            len++;
        }
        k = k % len;// 计算切分点
        if (k==0) return head;
        ListNode res = reverseNode(head);// 第一次翻转，翻转整个链表
        cur = res;
        for (int i=k; i>1; i--) {
            cur = cur.next;
        }
        ListNode cur2 = cur.next;
        cur.next = null;// 断链
        ListNode res1 = reverseNode(res);// 第二次翻转，翻转前k部分链表
        ListNode res2 = reverseNode(cur2);// 第三次翻转，翻转后k部分链表
        cur = res1;
        while (cur.next != null) cur = cur.next;
        cur.next = res2;// 重新链接
        return res1;
    }

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

两数相加

思路：两链表同时遍历，遇到空节点就补零。从最低位（即链表头部）相加，结果链表中每一位的值为x+y+carry的个位，如果发生进位，设置carry=1。如此遍历两个链表，最后检查是否carry==1，若是则添加最高位的1。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode res = new ListNode(-1);
        ListNode cur = res;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int x = (l1 == null)? 0: l1.val;
            int y = (l2 == null)? 0: l2.val;
            int num = x + y + carry;
            if (num > 9) {
                carry = 1;
                num = num % 10;
            } else carry = 0;
            cur.next = new ListNode(num);
            cur = cur.next;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        if (carry == 1) cur.next = new ListNode(1);
        return res.next;
    }
}

合并K个排序链表

思路：将两个有序链表链表排序很简单。使用归并排序的思想，将多个链表先切分再两两合并，最终可得排序的链表。时间复杂度为O(n*log(k))，其中n为链表平均长度，k为链表个数；空间复杂度O(1)。

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length==0) return null;
        return merge(lists, 0, lists.length-1);
    }

    public ListNode merge(ListNode[] lists, int left, int right) {
        if (left==right) return lists[left];
        int mid = (left+right)/2;
        ListNode leftNode = merge(lists, left, mid);
        ListNode rightNode = merge(lists, mid+1, right);
        return mergeTwoLists(leftNode, rightNode);
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1==null) return list2;
        if (list2==null) return list1;
        if (list1.val>list2.val) {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
        else {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }
    }
}