# LeetCode基础算法-链表

LeetCode 链表

---

1. 删除链表中的节点

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。

解题思路：

1. 使用赋值取代法来实现删除节点，1-2-3，假设我们要删除1节点，我们首先将2节点的值赋值给1节点，然后将1节点的next指定为3节点jie'k
2. node.val = node.next.val;
3. node.next = node.next.next

    public void deleteNode(ListNode node) {
        if (node == null || node.next == null) {
            node = null;
            return;
        }
        ListNode next = node.next;
        node.val = next.val;
        node.next = node.next.next;
    }

---

2. 删除倒数第n个节点

给定一个链表，删除链表的倒数第n个节点，并且返回链表的头结点。

解题思路：
我们假设链表一共N个节点。

1. 使用快慢两个指针来解决寻找倒数第n个节点，找到之后删除该节点即可。
2. 快指针:先行n步。
3. 慢指针执行头节点，快指针前进N-n-1到达终点 ,慢指针前进N-n-1步到达待删除节点的前一个节点。
4. 删除倒数第n个节点即可。

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode first = head;
        // 先向前行驶n个单元
        while (n-- != 0) {
            first = first.next;
        }
        if (first == null) {
            return head.next;
        }
        ListNode second = head;
        // first继续向前size-n-1个单元
        // second向前前进size-n-1个单元，second为待删除的前一个元素
        while (first.next != null) {
            first = first.next;
            second = second.next;
        }
        // second.next本来指向待删除的节点
        second.next = second.next.next;
        return head;
    }

---

3. 反转链表

反转一个单链表。

解题思路

1. 使用双指针法来解决问题。
2. pre指针指向已反转完成的链表头节点，head指向待翻转链表的头节点。
3. 遍历head，将待反转节点的next指向pre。

    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode next = null;
        // head总是指向待反转元素
        while (head != null) {
            // 首先保存待反转节点的下一个节点
            next = head.next;
            // 加入已反节点链表中
            head.next = pre;
            // pre矫正
            pre = head;
            // head矫正
            head = next;
        }

        return pre;
    }

---

4. 合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

解题思路：

1. 使用两个指针，循环遍历合并即可。

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode result = new ListNode(0);
        ListNode dumpy = result;

        ListNode left = l1;
        ListNode right = l2;
        while (left != null && right != null) {
            int leftVal = left.val;
            int rightVal = right.val;
            if (leftVal < rightVal) {
                dumpy.next = left;
                dumpy = dumpy.next;
                left = left.next;
            } else {
                dumpy.next = right;
                dumpy = dumpy.next;
                right = right.next;
            }
        }

        if (left != null) {
            dumpy.next = left;
        }

        if (right != null) {
            dumpy.next = right;
        }
        return result.next;
    }

---

5. 回文链表

请判断一个链表是否为回文链表。

解题思路：

1. 使用快慢指针+反转链表的思路来解决问题。
2. 使用快慢指针来查找链表的中点，反转中点后的值，并拼接中点前的值。
3. 比较head-中点和中点-末尾的值是否相等。
4. 1-2-3-2-1>>>1-2-3-1-2.

    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        slow.next = reverseList(slow.next);
        slow = slow.next;
        while (slow != null) {
            if (head.val != slow.val) {
                return false;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }

---

6. 环形链表

给定一个链表，判断链表中是否有环.

解题思路：

1. 使用快慢指针来解决问题。，如果存在环，那么快慢指针必会相遇。

    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return true;
        }

        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }