LinkedList例题分析

-- O（1）删除链表节点

    >> 题目：如何在O（1）时间复杂度和空间的条件下，删除某个节点。

    >> 解题思路：如果直接删除该节点，需要O(n)的时间复杂度来寻找前一个节点，显然不能达到要求；那么就不能采用该方法，寻找后继节点，将后继节点中的内容拷贝到该节点，然后删除后继节点。这样只有在删除最后节点的时候，需要遍历链表寻找其前一个节点。

-- Swap Nodes in Pair

    >> 题目：将链表中相邻另个节点交换顺序。    

    >> 解题思路：两两一组交换node的内容。

-- Sort List ？

    >> 题目：对链表进行排序，要求时间复杂度为O(n * logn)，空间为常数

    >> 解题思路：归并排序。

    public ListNode sortList(ListNode head) {

        return mergeSort(head);
    }

    private ListNode mergeSort(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode slow = head, fast = head;
        // when head is a 2 ele data, this is ok;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        fast = slow.next;
        slow.next = null;
        slow = mergeSort(head);
        fast = mergeSort(fast);
        return merge(slow, fast);
    }

    private ListNode merge(ListNode head1, ListNode head2) {
        ListNode helper = new ListNode(0);
        helper.next = head1;
        ListNode pre = helper;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                head1 = head1.next;
            } else {
                ListNode next = head2.next;
                head2.next = pre.next;
                pre.next = head2;
                head2 = next;
            }
            pre = pre.next;
        }
        if (head2 != null) {
            pre.next = head2;
        }
        return helper.next;
    }

-- Rotate List
    >> 题目：将给定链表中的后k个数，移到链表前面
    >> 解题思路：主要处理溢出问题，首先得到链表的长度，求余，对于0的直接返回，其余的移动

    public ListNode rotateRight(ListNode head, int n) {
        if (head == null || n == 0) return head;
        ListNode slow = head, fast = head, temp = null;
        int count = 1;

        while (fast != null) {
            fast = fast.next;
            count++;
        }
        n = n % count;
        if (n == 0) return head;
        fast = head;

        int i = 0;
        for (i = 0; i < n && fast != null; i++) {
            fast = fast.next;
        }
        if (fast == null) {
            return head;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        temp = slow.next;
        slow.next = null;
        fast.next = head;
        return temp;
    }

-- Reverse Nodes in k-Group

    >> 题目：将链表的每k个为一组进行逆序

    >> 解题思路：比较简单的是值交换。使用栈。

-- Reverse Listed List II

    >> 题目：将链表中的某一段进行逆序

    >> 解题思路：目前的实现也是值交换，使用栈。

-- Remove Nth Node From End of List

    >> 题目：删除链表中倒数第n个node

    >> 解题思路：遍历，将其转换成正向的，然后删除。

-- Remove Duplicates from Sorted List II

    >> 题目：从排序链表中删除重复的。

    >> 解题思路：遍历， 注意特殊情况。

-- Partition List

    >> 题目：调整链表的顺序，使链表中比x小的节点全部都放在前面，但是得保持其在原始链表中的顺序。

    >> 解题思路：遍历，注意使用简单删除中的顺序问题。

-- Merge Two Sorted Lists

    >> 题目：将两个排好序的链表合并

    >> 解题思路：合并，但是越简单越好，也就是使用额外的首节点。

-- Merge K Sorted Lists

    >> 题目：将k个list排序

    >> 解题思路：合并，调用Merge Two Sorted Lists

-- Linked List Cycle

    >> 题目：判断链表中是否有环

    >> 解题思路：两个指针遍历，速度不同。

    

-- Linked List Cycle II

    >> 题目：判断链表中是否有环，并返回环的起点。

    >> 解题思路：注意如果一开始就入环，处理方法不太一样，所有的需要加个前缀节点，使两种情况归一化。

-- Intersection of Two Linked Lists 

    >> 题目：输出两个链表的交叉区域

    >> 解题思路：先遍历，统计两个链表的数量，并判断是否有交叉，然后根据交叉数计算开始位置。遍历，找到真正的起始位置

-- Insertion Sort List

    >> 题目：插入排序链表

-- Copy List with Random Pointer 

    >> 题目：copy链表，但是这个链表，有两个指针，一个指向后继节点，另一个指向随机节点

    >> 解题思路：遍历，生成map，再遍历，设置指针

-- sorted List to BST

    >> 题目：从排序链表，生成BST

    >> 解题思路：递归，每个可以从头查找，这个不是最大的限制因素。