Leetcode链表总结

    由于最近开始面临保研找实习，所以打算刷波leetcode，之前一直想做这件事，巩固一下自己的基础，但总是被各种事情耽搁，由此写下这篇博客作为督促。在这期间偶然间看到同学的博客，他也打算刷leetcode，但刚做了一题就拿到了滴滴的offer，而且那一题跟我做的第一道题一样，让人感叹的巧合。希望我也能像他一样得到满意的结果。

    本篇文章不会包含代码的讲解，只是做题目的一点思路心得，相关答案可以访问leetcode

2. Add Two Numbers

比较简单的链表相加问题，除了要考虑到链表不一样长的情况，还有最高位进位为1。思考到细节。

另外，在solution中看到了为链表加空表头的方式，解决了插入判断一致性问题，也是一个比较基础的操作。

19. Remove Nth Node From End of List

删除倒数第n个节点，双指针问题，第一个指针走n步，第二个指针与第一个指针一起移动，需考虑删除节点为头节点的情况。也可通过添加一空头，消除头节点的特殊判断。

24. Swap Nodes in Pairs

交换相邻节点，添加空头消除头节点特殊情况，考虑链表长度为奇数的特殊情况。

82. Remove Duplicates from Sorted List II

有序表删除重复元素，按值找出需删除的一段链表，修改指针，添加空头消除头节点特殊判断。

92. Reverse Linked List II

在206题反转链表的基础上，在链表上加入某范围的反转，反转链表使用三个指针，从头到尾依次把后一块移动到前一块。由于反转的是链表的部分，头部有可能改变也可能不改变，因此加入空头消除特殊性，small和big指针分别记录需反转链表的前一块和后一块的地址，之后使用206题方法对链表进行反转即可。

看了讨论区，发现也不用计算链表末尾值，根据n-m即可知道移动块的次数，少了一次需反转链表的遍历。

109. Convert Sorted List to Binary Search Tree

将有序链表转换为平衡BST树，采用递归的方式，链表中部元素作为树根，左右子树依次对两端链表进行同种操作，寻找中部元素使用两个指针，一个一次走一步，另一个一次走两步，即可找到中部元素，代码如下

public TreeNode sortedListToBST(ListNode head) {
        if(head==null) return null;
        ListNode fast=head;
        ListNode slow=head;
        ListNode pre=head;
        while(fast!=null&&fast.next!=null) {  //快指针走到尾部时
            pre=slow;
            slow=slow.next;
            fast=fast.next.next;
        }
        pre.next=null; //将链表断开
        TreeNode treehead = new TreeNode(slow.val); //new一根节点
        if(head==slow) return treehead;  //只剩一个节点不进行递归
        else {
            treehead.left=sortedListToBST(head);
            treehead.right=sortedListToBST(slow.next);
        }
        return treehead;
    }

看到讨论区中有不将链表断开，另写一个函数传入tail，将null判断改为是否等于tail判断，少了一个指针。

138. Copy List with Random Pointer

random指针链表深拷贝，一直在考虑如何找到重复节点，其实也是一个索引问题，使用hashmap，被拷贝链表作为key，拷贝节点为value，从头开始一一连接指针即可。

public RandomListNode copyRandomList(RandomListNode head) {
        Map<RandomListNode,RandomListNode> map = new HashMap<>();
        //第一次遍历做映射
        RandomListNode tmp = head;
        while(tmp!=null) {
            map.put(tmp,new RandomListNode(tmp.label));
            tmp=tmp.next;
        }
        //第二次遍历做连接
        tmp=head;
        while(tmp!=null) {
            map.get(tmp).next=map.get(tmp.next);
            map.get(tmp).random=map.get(tmp.random);
            tmp=tmp.next;
        }
        
        return map.get(head);
    }

142. Linked List Cycle II

在141判断是否有环形链表的基础上，返回入环的第一个节点。在不使用另外存储空间的情况下。判断环形链表使用双指针，一个一次走两步，另一个一次走一步，如果链表中有环，那么指针会相遇。返回入环的第一个节点需要数学推导，即当两指针相遇后，将一个指针退回head，之后各自走一步，再次相遇时便是入环的第一个节点。

public ListNode detectCycle(ListNode head) {
        ListNode first = head;
        ListNode second = head;
        boolean flag=false;
        while(second!=null&&second.next!=null) {  //无环为null返回
            first=first.next;
            second=second.next.next;
            if(first==second) {
                flag=true;
                break;
            }
        }
        if(flag==false)
            return null;
        else {
            first=head;
            while(first!=second) {
                first=first.next;
                second=second.next;
            }
            return first;
        }
    }

143. Reorder List

重排链表，这道题给我一种“妙啊”的感觉，后一半反排插入一开始不知道怎么办，甚至想到了hash，讨论区的做法是，先把后一半反转，再逐个插入。

public void reorderList(ListNode head) {
        if(head==null||head.next==null||head.next.next==null) return;
        ListNode fast=head;
        ListNode slow=head;
        //找到一半
        while(fast!=null&&fast.next!=null) {
            fast=fast.next.next;
            slow=slow.next;
        }
        //反转
        ListNode first = slow.next;
        ListNode second = first.next;
        slow.next=null;
        first.next=null;
        while(second!=null) {
            ListNode third = second.next;
            second.next=first;
            first=second;
            second=third;
        }
        //逐个插入
        ListNode tmp=head;
        ListNode next=null;
        while(first!=null) {
            next=first.next;
            first.next=tmp.next;
            tmp.next=first;
            tmp=tmp.next.next;
            first=next;
        }
    }

148. Sort List

在O(nlogn)时间内排序，归并排序加递归，将链表分为两半，递归排序，再将这两半排好序的链表合并在一起。

public ListNode sortList(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode fast = head;
        ListNode slow = head;
        //链表分半
        while(fast.next!=null&&fast.next.next!=null) {
            fast=fast.next.next;
            slow=slow.next;
        }
        //递归排序
        ListNode tmp=slow.next;
        slow.next=null;
        ListNode left=sortList(head);
        ListNode right=sortList(tmp);
        //合并
        ListNode blank=new ListNode(0);
        tmp=blank;
        while(left!=null&&right!=null) {
            if(left.val<right.val) {
                tmp.next=left;
                left=left.next;
                tmp=tmp.next;
            }else {
                tmp.next=right;
                right=right.next;
                tmp=tmp.next;
            }
        }
        if(left!=null)
            tmp.next=left;
        if(right!=null)
            tmp.next=right;
        return blank.next;
    }

总结：

在链表头部添加空头以消除头部特殊判断比较常见，双指针问题可用于倒数k个或将链表元素分半。递归和hashmap也比较常见。