二链表

基本功1，翻转链表

206. Reverse Linked List

循环外2根指针，循环内NEXT指针。

public ListNode reverseList(ListNode head) {
        ListNode pre  = null;
        ListNode cur = head;
        if(cur == null) return null;
        while(cur!=null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
            
        }
        return pre;
    }

92. Reverse Linked List II

https://leetcode.com/problems/reverse-linked-list-ii/description/
在翻转链表的基础上引入哨兵节点，来简化代码复杂性。然后就是在纸上推敲，移指针的过程。

public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode s = new ListNode(0);
        s.next = head;
        ListNode pre = s;
        ListNode cur = s.next;
        for(int i=1;i<m;i++){
            pre = cur;
            cur = cur.next;
        }
        ListNode begin = pre;
        pre = pre.next;
        cur = cur.next;
        for(int i=m;i<n;i++){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        begin.next.next = cur;
        begin.next = pre;
        return s.next;
    }

基本功2，双指针

83. Remove Duplicates from Sorted List

https://leetcode.com/problems/remove-duplicates-from-sorted-list/description/
2个值相等，就前一个的NEXT指针指到后一个的NEXT。后一个指针往后移一位。不相等，就2个同时向后移。

public ListNode deleteDuplicates(ListNode head) {
        if(head==null)
            return null;
        ListNode pre = head;
        ListNode p = head.next;
        while(p!=null){
            if(pre.val==p.val){
                pre.next = p.next;
                p = p.next;
            }else{
                pre = pre.next;
                p = p.next;
            }
        }
        return head;
    }

86. Partition List

https://leetcode.com/problems/partition-list/description/
这道题的核心在于，要断开原先链表里的指针。不然最后输出答案的时候会有环。

public ListNode partition(ListNode head, int x) {
        ListNode small = new ListNode(0);
        ListNode big = new ListNode(0);
        ListNode p = head;
        ListNode smallp = small;
        ListNode bigp = big;
        while(p!=null) {
            if(p.val<x){
                smallp.next = p;
                smallp = smallp.next;
            }else{
                bigp.next = p;
                bigp = bigp.next;
            }
            ListNode next = p.next;
            p.next = null;
            p = next;
            
        }
        smallp.next = big.next;
        return small.next;
    }

328. Odd Even Linked List

https://leetcode.com/problems/odd-even-linked-list/description/
2个指针套路，画图求解。

public ListNode oddEvenList(ListNode head) {
        if(head == null) return null;
        ListNode even = head.next, evenp = even;
        ListNode odd = head, oddp = odd;
        if(even == null) return head;
        ListNode p = even.next;
        int i = 3;
        while(p != null) {
            if(i%2==1){
                oddp.next = p;
                oddp = oddp.next;
            }else{
                evenp.next = p;
                evenp = evenp.next;
            }
            p = p.next;
            i++;
        }
        oddp.next = even;
        evenp.next = null;
        return head;
    }

2. Add Two Numbers

https://leetcode.com/problems/add-two-numbers/description/

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode res = new ListNode(0);
        ListNode p = res;
        ListNode p1 = l1, p2 = l2;
        int sum = 0;
        while(p1!=null || p2!=null){
            if(p1!=null){
                sum+=p1.val;
                p1 = p1.next;
            } 
            if(p2!=null){
                sum+=p2.val;
                p2 = p2.next;
            } 
            p.next = new ListNode(sum%10);
            sum = sum/10;
            p = p.next;
        }
        if(sum==1)
            p.next = new ListNode(1);
        return res.next;
    }

445. Add Two Numbers II

https://leetcode.com/problems/add-two-numbers-ii/description/
相比较上一题，先用栈做个翻转。之后同样的套路。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> s1= new Stack<>();
        Stack<Integer> s2= new Stack<>();
        while(l1!=null){
            s1.push(l1.val);
            l1 = l1.next;
        }
        while(l2!=null){
            s2.push(l2.val);
            l2 = l2.next;
        }
        ListNode cur = null;
        ListNode pre = null;
        int sum = 0;
        while(!s1.isEmpty() || !s2.isEmpty()) {
            if(!s1.isEmpty()) sum+=s1.pop();
            if(!s2.isEmpty()) sum+=s2.pop();
            pre = cur;
            cur = new ListNode(sum%10);
            sum = sum/10;
            cur.next = pre;
        }
        if(sum==1){
            pre = cur;
            cur = new ListNode(1);
            cur.next = pre;
        }
        return cur;
        
    }

基本功3，虚拟头结点

203. Remove Linked List Elements

https://leetcode.com/problems/remove-linked-list-elements/description/

public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = head;
        while(cur!=null){
            if(cur.val == val){
                pre.next = cur.next;
            }else{
                pre = cur;
            }
            cur = cur.next;
        }
        return dummy.next;
    }

82. Remove Duplicates from Sorted List II

https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/description/
这道题非常不如意写对。核心思路就是删除所有重复节点。我们用PRE保存PRE前面都是不含重复节点的点。pre后面是未知的。我们进WHILE循环用CUR 去遍历，如果有重复节点CUR就往后走。知道走到最后一个重复节点。这个时候我们看PRE.NEXT==CUR ，是的话，代表没重复。2边指针都往前走一步。如果不是的话。我们把那组重复节点删去。

public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0);

        dummy.next = head;
        if(head == null) return null;
        ListNode pre = dummy;
        ListNode cur = head;
        while(cur!=null){
            while(cur.next!=null && cur.val == cur.next.val){
                cur = cur.next;
            }//cur will be last node or repeat number last node
            if(pre.next == cur){
                pre = cur;
            }
            else{
                pre.next = cur.next;
            }
            cur = cur.next;
            
        }
        return dummy.next;
    }

21. Merge Two Sorted Lists

https://leetcode.com/problems/merge-two-sorted-lists/description/

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode p = head;
        while(l1!=null && l2!=null){
            int i1 = l1.val;
            int i2 = l2.val;
            if(i1<i2){
                p.next = new ListNode(i1);
                l1 = l1.next;
            }else{
                p.next = new ListNode(i2);
                l2 = l2.next;
            }
            p = p.next;
        }
        if(l1!=null){
            p.next = l1;
        }
        if(l2!=null){
            p.next = l2;
        }
        return head.next;
    }

24. Swap Nodes in Pairs

https://leetcode.com/problems/swap-nodes-in-pairs/description/

public ListNode swapPairs(ListNode head) {
        if(head == null || head.next==null) return head; 
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = head;
        ListNode cur2 = head.next;
        while(cur!=null && cur2!=null) {
            ListNode next = cur2.next;
            cur2.next = cur;
            pre.next = cur2;
            cur.next = next;
            pre = cur;
            cur = cur.next;
            if(cur==null) break;
            cur2 = cur.next;
        }
        return dummy.next;
    }

147. Insertion Sort List

https://leetcode.com/problems/insertion-sort-list/description/
链表的插入排序的核心，就是从DUMMY节点，往前走，找到第一个大于等于它的值。去这个值的前面一个节点。然后做一个穿针引线。作为穿针引线后，CUR就去之前下一个，然后重新做。

public ListNode insertionSortList(ListNode head) {
        ListNode cur = head, next = null;
        ListNode dummy = new ListNode(0);
        while(cur!=null){
            ListNode p = dummy;
            next = cur.next;
            while(p.next!=null && p.next.val<cur.val)
                p = p.next;
            cur.next = p.next;
            p.next = cur;
            cur = next;
        }
        return dummy.next;
    }

19. Remove Nth Node From End of List

https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/
先用2个指针把偏移量移好，这样当后面那个指针移到NULL时前面那个指针刚好可以删除节点。

public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pos = dummy;
        while(n>=0){
            pos = pos.next;
            n--;
        }
        ListNode pre = dummy;
        while(pos!=null){
            pos = pos.next;
            pre = pre.next;
        }
        pre.next = pre.next.next;
        return dummy.next;
    }

61. Rotate List

https://leetcode.com/problems/rotate-list/description/

public ListNode rotateRight(ListNode head, int k) {
        int l = getLen(head);
        if(l == 0) return head;
        k = k%l;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode tail = dummy;

        int n = k;
        while(n >= 1) {
            tail = tail.next;
            n--;
        }
        ListNode pos = tail.next;
        ListNode pre = dummy;
        while(pos!=null){
            pre = pre.next;
            tail = tail.next;
            pos = pos.next;
        }
        tail.next = head;
        dummy.next = pre.next;
        pre.next = null;
        return dummy.next;
        
    }
    private int getLen(ListNode head){
        int l = 0;
        while(head!=null){
            head = head.next;
            l++;
        }
        return l;
    }

基本功4，快满指针找中点或环，MERGE LIST

142. Linked List Cycle II

https://leetcode.com/problems/linked-list-cycle-ii/description/

public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast) break;
        }
        if(fast==null || fast.next==null) return null;
        ListNode begin = head;
        while(begin!=slow){
            begin = begin.next;
            slow = slow.next;
        }
        return slow;
    }

148. Sort List

https://leetcode.com/problems/sort-list/description/

public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }//slow is the mid;
        fast = slow.next;
        slow.next = null;
        ListNode l1 = sortList(head);
        ListNode l2 = sortList(fast);
        return merge(l1,l2);
        
    }

    private ListNode merge(ListNode l1,ListNode l2) {
        ListNode p1 = l1;
        ListNode p2 = l2;
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        while(p1!=null && p2!=null){
            if(p1.val<p2.val){
                p.next = p1;
                p1 = p1.next;
            }else{
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }
        if(p1!=null) p.next = p1;
        if(p2!=null) p.next = p2;
        return dummy.next;
    }

143. Reorder List

https://leetcode.com/problems/reorder-list/description/
1.找中点 2.翻转链表 3.MERGE

public void reorderList(ListNode head) {
        ListNode slow = head;
        if(head == null || head.next == null) return;
        ListNode fast = head.next;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }//slow is the mid;
        fast = slow.next;
        slow.next = null;
        
        //reverse fast list
        ListNode pre = fast;
        ListNode cur = fast.next;
        fast.next = null;
        while(cur!=null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        
        ListNode l2 = pre;
        ListNode l1 = head;
        //merge
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        while(l1!=null && l2!=null){
            p.next = l1;
            l1 = l1.next;
            p = p.next;
            p.next = l2;
            l2 = l2.next;
            p = p.next;
        }
        if(l1!=null) p.next = l1;
    }
    private void pt(ListNode l){
        while(l!=null){
            System.out.print(l.val+",");
            l = l.next;
        }
        System.out.println();
    }

234. Palindrome Linked List

https://leetcode.com/problems/palindrome-linked-list/description/
1.找中点 2.翻转链表 3.判断链表值相等

public boolean isPalindrome(ListNode head) {
        ListNode slow = head;
        if(head == null || head.next == null) return true;
        ListNode fast = head.next;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }//slow is the mid;
        fast = slow.next;
        slow.next = null;
        
        ListNode pre = fast;
        ListNode cur = fast.next;
        fast.next = null;
        while(cur!=null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        
        ListNode l2 = pre;
        ListNode l1 = head;
        while(l1!=null && l2!=null){
            if(l1.val != l2.val) return false;
            l1 = l1.next;
            l2 = l2.next;
        }
        return true;
    }

链表其他

237. Delete Node in a Linked List

https://leetcode.com/problems/delete-node-in-a-linked-list/description/
因为拿不到要删除节点的前一个节点了，所以直接把后面的节点的值复制过来，然后删除后面的节点。

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

138. Copy List with Random Pointer

https://leetcode.com/problems/copy-list-with-random-pointer/description/
这道题的思想，就是链表交错穿插好。
p.next.random = p.random.next(random!=null的前提下）
最后把2个链表给解开。解开的时候，第2个链表（也就是深拷贝的链表，需要单独对NULL做判断，不然。next .next 会抛出空指针异常）

public RandomListNode copyRandomList(RandomListNode head) {
        if(head == null) return null;
        RandomListNode p = head;
        
        while(p!=null){
            RandomListNode p2 = new RandomListNode(p.label);
            RandomListNode next = p.next;
            p.next = p2;
            p = next;
            p2.next = p;
        }
        
        p = head;
        while(p!=null){
            if(p.random!=null){
                p.next.random = p.random.next;
            }
            p = p.next.next;
        }
        RandomListNode ori = head;
        RandomListNode res = head.next;
        p = res;
        while(p!=null && ori!=null){
            ori.next = ori.next.next;
            ori = ori.next;
            if(p.next == null) break;
            p.next = p.next.next;
            p = p.next;
        }
  
        return res;
    }

725. Split Linked List in Parts

https://leetcode.com/problems/split-linked-list-in-parts/description/

public ListNode[] splitListToParts(ListNode root, int k) {
        ListNode[] res = new ListNode[k];
        if(k==0) return res;
        int l = getLen(root);
        if(k>=l){
            ListNode cur = root;
            int i = 0;
            while(l>0){
                ListNode next = cur.next;
                cur.next = null;
                res[i++] = cur;
                cur = next;
                l--;
            }
        }else{
            int yu = l%k;
            int sh = l/k;
            ListNode cur = root;
            for(int i=0;i<k;i++){
                res[i] = cur;
                while(sh>1){
                    cur = cur.next;
                    sh--;
                }
                sh = l/k;
                if(yu>0){
                    yu--;
                    cur = cur.next;
                }
                ListNode n = cur.next;
                cur.next = null;
                cur = n;
            }
        }
        return res;
    }
    private int getLen(ListNode h){
        int l = 0;
        while(h!=null){
            h = h.next;
            l++;
        }
        return l;
    }

817. Linked List Components

https://leetcode.com/problems/linked-list-components/description/

public int numComponents(ListNode head, int[] G) {
        Set<Integer> s = new HashSet<>();
        for(int i:G){
            s.add(i);
        }
        ListNode p = head;
        int res = 0;
        while(p!=null){
            if(s.contains(p.val)){
                while(p!=null && s.contains(p.val)){
                    p = p.next;
                }
                res++;
            }else{
                p = p.next;
            }
        }
        return res;
    }

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 219,869评论 6赞 508
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 93,716评论 3赞 396
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 166,223评论 0赞 357
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 59,047评论 1赞 295
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 68,089评论 6赞 395
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,839评论 1赞 308
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,516评论 3赞 420
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,410评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,920评论 1赞 319
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 38,052评论 3赞 340
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 40,179评论 1赞 352
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,868评论 5赞 346
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,522评论 3赞 331
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 32,070评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 33,186评论 1赞 272
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,487评论 3赞 375
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 45,162评论 2赞 356

二 链表