难度：Eazy

面试题 02.02. 返回倒数第 k 个节点

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

注意：本题相对原题稍作改动

示例：

输入： 1->2->3->4->5 和 k = 2

输出： 4

说明：给定的 k 保证是有效的。

思路1：两次遍历

1.第一次遍历数组，统计链表中元素个数Count

2.第二次遍历数组,用Pos表示当前元素位置，当Pos = Count - K时，return val

    public int kthToLast(ListNode head, int k) {
        int count = 0;
        ListNode cur = head;
        while(cur != null) {
            cur = cur.next;
            count++;
        }
        int pos = 0;
        while(head != null){
            if(pos++ == count - k) return head.val;
            head = head.next;
        }
        return 0;
    }

思路2：双指针

1.令指针p先走k步

2.令指针q = head

3.q = q.next， p = p.next，当p == null，返回q

public int kthToLast(ListNode head, int k) {
        ListNode cur = head;
        while(--k >0) cur = cur.next;
        ListNode pre = head;
        while(cur.next != null){
            cur = cur.next;
            pre = pre.next;
        }
        return pre.val;
    }

面试题 02.03. 删除中间节点

实现一种算法，删除单向链表中间的某个节点（即不是第一个或最后一个节点），假定你只能访问该节点。

示例：

输入：单向链表a->b->c->d->e->f中的节点c

结果：不返回任何数据，但该链表变为a->b->d->e->f

思路：因为删除的既不是第一个节点也不是最后一个节点，所以可以保证 待删除节点的后继节点不为空，所以仅需将该节点的值设为后继节点的值，并将该节点的的next设置为该节点的后继节点的后继节点即可。

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

21. 合并两个有序链表

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

示例：

输入：1->2->4, 1->3->4

输出：1->1->2->3->4->4

思路：创建新节点head,设置l1和l2分别代表两个待合并链表的头部，比较l1和l2的大小，将较小元素设置为head.next && head = head.next，同时较小节点的指针后移。

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

234. 回文链表

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

示例 1:

输入: 1->2

输出: false

示例 2:

输入: 1->2->2->1

输出: true

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

思路1：

双端队列。

public boolean isPalindrome(ListNode head) {
        ListNode p = head;
        Deque<Integer> que = new LinkedList();
        while(p != null){
            que.offer(p.val);
            p = p.next;
        }
        while(que.size() != 0 && que.size() != 1){
            if(!que.pollFirst().equals(que.pollLast()))
                return false;
        }
        return true; 
    }

思路2：

快慢指针。注意，这段代码及其优雅。这里面包括了几个常用技巧：

1、在使用快慢指针时，若链表长度为偶数，则慢指针指向len(list)/2 + 1个节点，若链表长度为奇数，则指向中间节点：

1 -> 2 -> 3 -> 4中，指向3

1 -> 2 -> 3 -> 4 ->5中，指向3

2、若节点个数为奇数，则slow指针需要 = slow.next，以保证slow指针和fast指针的初始节点相同

3、翻转链表时，需要先定义头结点为null，同时定义后继节点为tmp

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

剑指 Offer 18. 删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

注意：此题对比原题有改动

示例 1:

输入: head = [4,5,1,9], val = 5

输出: [4,1,9]

解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2:

输入: head = [4,5,1,9], val = 1

输出: [4,5,9] 解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

思路：依次遍历，设置前驱结点pre，当cur节点的值等于val时，pre = cur.next即可。

public ListNode deleteNode(ListNode head, int val) {
        ListNode cur = head;
        ListNode pre =  new ListNode(0);
        while(cur != null){
            if(cur.val == val){
                pre.next = cur.next;
                break;
            }
            pre = cur;
            cur = cur.next;
        }
        return head.val == val ? pre.next : head;
    }

876. 链表的中间结点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5]

输出：此列表中的结点 3 (序列化形式：[3,4,5])

返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。

注意，我们返回了一个 ListNode 类型的对象 ans，这样：

ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：

输入：[1,2,3,4,5,6]

输出：此列表中的结点 4 (序列化形式：[4,5,6])

由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

思路：快慢指针，非常容易，不再介绍。

public ListNode middleNode(ListNode head) {
        ListNode p = head, q = head;
        while(q != null && q.next != null){
            q = q.next.next;
            p = p.next;
        }
        return p;
    }

203. 移除链表元素

删除链表中等于给定值 val 的所有节点。

示例:

输入: 1->2->6->3->4->5->6, val = 6

输出: 1->2->3->4->5

思路：简单遍历，找到val后用while去除所有重复元素即可。

public ListNode removeElements(ListNode head, int val) {
        ListNode pre = new ListNode(-1);
        ListNode cur = head;
        while(cur != null){
            if(cur.val == val){
                pre.next = cur.next;
                cur = cur.next;
                continue;
            }
            pre = cur;
            cur = cur.next;
        }
        cur = head;
        while(cur!= null && cur.val == val) cur = cur.next;
        return cur;
    }

剑指 Offer 52. 两个链表的第一个公共节点

输入两个链表，找出它们的第一个公共节点。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3

输出：Reference of the node with value = 8

输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

『优雅警告！』

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p = headA;
        ListNode q = headB;
        while(p != q){
            p = p != null ? p.next : headB;
            q = q != null ? q.next : headA;
        }
        return p == q ? p : null;
    }

206. 反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL

输出: 5->4->3->2->1->NULL

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

1290. 二进制链表转整数

给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。

请你返回该链表所表示数字的十进制值。

示例 1：

输入：head = [1,0,1]

输出：5

解释：二进制数 (101) 转化为十进制数 (5)

示例 2：

输入：head = [0]

输出：0

示例 3：

输入：head = [1]

输出：1

示例 4：

输入：head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]

输出：18880

示例 5：

输入：head = [0,0]

输出：0

思路：利用Integer中的parseInt(sb.toString(), 2)将2进制string转化为10进制int

    public int getDecimalValue(ListNode head) {
        StringBuilder sb = new StringBuilder();
        while(head != null){
            sb.append(head.val);
            head = head.next;
        }
        return Integer.parseInt(sb.toString(), 2);
    }

141. 环形链表

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

思路1：

    #快慢指针
    public boolean hasCycle(ListNode head) {
        ListNode p = head, q = head;
        while(q != null && q.next != null){
            p = p.next;
            q = q.next.next;
            if(p == q)
                return true;
        }
        return false;
    } 

思路2：取巧

    public boolean hasCycle(ListNode head) {
        ListNode p = head;
        while(p != null){
            if(p.val == Integer.MAX_VALUE) return true;
            p.val = Integer.MAX_VALUE;
            p = p.next;
        }
        return false;
    } 

面试题 02.01. 移除重复节点

编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

示例1:

输入：[1, 2, 3, 3, 2, 1]

输出：[1, 2, 3] 示例2:

输入：[1, 1, 1, 1, 2]

输出：[1, 2]

提示：

链表长度在[0, 20000]范围内。链表元素在[0, 20000]范围内。

    public ListNode removeDuplicateNodes(ListNode head) {
        if (head == null) return head;
        Set<Integer> occurred = new HashSet<Integer>();
        occurred.add(head.val);
        ListNode pos = head;
        while (pos.next != null) {
            ListNode cur = pos.next;
            if (occurred.add(cur.val))
                pos = pos.next;
            else 
                pos.next = pos.next.next;
        }
        pos.next = null;
        return head;
    }

1474. 删除链表 M 个节点之后的 N 个节点

给定链表 head 和两个整数 m 和 n. 遍历该链表并按照如下方式删除节点:

开始时以头节点作为当前节点. 保留以当前节点开始的前 m 个节点. 删除接下来的 n 个节点. 重复步骤 2 和 3, 直到到达链表结尾. 在删除了指定结点之后, 返回修改过后的链表的头节点.

进阶问题: 你能通过就地修改链表的方式解决这个问题吗?

示例 1:

输入: head = [1,2,3,4,5,6,7,8,9,10,11,12,13], m = 2, n = 3

输出: [1,2,6,7,11,12]

解析: 保留前(m = 2)个结点, 也就是以黑色节点表示的从链表头结点开始的结点(1 ->2).

删除接下来的(n = 3)个结点(3 -> 4 -> 5), 在图中以红色结点表示.

继续相同的操作, 直到链表的末尾.

返回删除结点之后的链表的头结点.

示例 2:

输入: head = [1,2,3,4,5,6,7,8,9,10,11], m = 1, n = 3

输出: [1,5,9]

解析: 返回删除结点之后的链表的头结点.

示例 3:

输入: head = [1,2,3,4,5,6,7,8,9,10,11], m = 3, n = 1

输出: [1,2,3,5,6,7,9,10,11]

示例 4:

输入: head = [9,3,7,7,9,10,8,2], m = 1, n = 2

输出: [9,7,8]

思路：简单模拟

    public ListNode deleteNodes(ListNode head, int m, int n) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode cur = head;
        while(cur != null){
            int cntM = 0;
            while(cur != null && cntM < m-1){
                cur = cur.next;
                cntM ++;
            }
            ListNode temp = cur;
            int cntN = 0;
            while(cur != null && cntN < n+1){
                cur = cur.next;
                cntN ++;
            }
            if(temp != null){
                temp.next = cur;
            }
        }
        return dummyHead.next;
    }

难度：Medium

61. 旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2

输出: 4->5->1->2->3->NULL

解释:

向右旋转 1 步: 5->1->2->3->4->NULL

向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:

输入: 0->1->2->NULL, k = 4

输出: 2->0->1->NULL

解释:

向右旋转 1 步: 2->0->1->NULL

向右旋转 2 步: 1->2->0->NULL

向右旋转 3 步: 0->1->2->NULL

向右旋转 4 步: 2->0->1->NULL

思路：

1、首先计算链表中节点数目为count，使k = count % k，这样可以减少很多不必要的计算。

2、将原问题转换为：将倒数k个节点移动至节点头部。

3、依次遍历数组，将第count - k个节点的next指针指向null，再将head节点设置为count - k + 1，当遍历至原链表尾部时，将尾部节点的next指向原链表的头部即可。

    public ListNode rotateRight(ListNode head, int k) {
        if(head == null) return head;
        int count = 0, pos = 0;
        ListNode cur = head, p = head;
        while(p != null){
            p = p.next;
            count ++;
        }
        p = head;
        k = k % count;
        if(k == 0) return head;
        while(cur != null){
            if(pos++ == count - k - 1){
                head = cur.next;
                cur.next = null;
                cur = head;
            }
            if(cur.next == null){
                cur.next = p;
                break;
            }
            cur = cur.next;
        } 
        return head;
  }

369. 给单链表加一

用一个非空单链表来表示一个非负整数，然后将这个整数加一。

你可以假设这个整数除了 0 本身，没有任何前导的 0。

这个整数的各个数位按照高位在链表头部、低位在链表尾部的顺序排列。

示例:

输入: [1,2,3]

输出: [1,2,4]

思路：这道题我采用的思路比较简单，就是先用一个栈保存链表中的所有元素，然后依次出栈（第一次出栈的元素 + 1），之后用carry 和 sum 保存进位和总和，逢使10进1，最后翻转链表即可。

    public ListNode plusOne(ListNode head) {
        Stack<Integer> stack = new Stack();
        ListNode cur = head;
        while(cur != null){
            stack.add(cur.val);
            cur = cur.next;
        }
        boolean flag = false;
        int carry = 0;
        cur = head;
        while(!stack.empty()){
            int sum = stack.pop() + (flag == false ? 1 : 0) + carry;
            flag = true;
            carry = sum / 10;
            sum = sum % 10;
            cur.next = new ListNode(sum);
            cur = cur.next;
        }
        cur.next = carry == 1 ? new ListNode(1) : null;
        return reverse(head.next);
    }
    ListNode reverse(ListNode head){
        ListNode pre = null;
        while(head != null){
            ListNode tmp = head.next;
            head.next = pre;
            pre = head;
            head = tmp;
        }
        return pre;
    }

445. 两数相加 II

给你两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

进阶：

如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例：

输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)

输出：7 -> 8 -> 0 -> 7

思路：这道题的思路跟上一道题非常相似，也是先进栈，然后依次出栈，逢10进1，区别是：

将上一题的单个链表转化成了两个链表。
最后的结果不需要翻转。

    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, ans = null;
        int carry = 0;
        while(!s1.empty() || !s2.empty()){
            int n1 = s1.empty() ? 0 : s1.pop();
            int n2 = s2.empty() ? 0 : s2.pop();
            int sum = n1 + n2 + carry;
            carry = sum/10;
            sum %= 10;
            ans = new ListNode(sum);
            ans.next = cur;
            cur = ans;
        }
        if(carry == 1){
            ans = new ListNode(1);
            ans.next = cur;
        }
        return ans;
    }

24. 两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

输入：head = [1,2,3,4]

输出：[2,1,4,3]

示例 2：

输入：head = []

输出：[]

示例 3：

输入：head = [1]

输出：[1]

思路：这道题思路上比较简单，主要考察的是链表操作的基本功，依次两两交换即可。

    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;
        while (temp.next != null && temp.next.next != null) {
            ListNode node1 = temp.next;
            ListNode node2 = temp.next.next;
            temp.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            temp = node1;
        }
        return dummyHead.next;
    }

143. 重排链表

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3.

示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

思路：这道题考察的知识点比较多，先用快慢指针将链表断开，然后reverse链表的后半部分，最后合并链表。

    public void reorderList(ListNode head) {
        ListNode pre = new ListNode(0), slow = head, fast = head;
        pre.next = head;
        while(fast!= null && fast.next != null){
            slow = slow.next;
            pre = pre.next;
            fast = fast.next.next;
        }
        if(fast != null){
            pre = pre.next;
            slow = slow.next;
            pre.next = null;
        } else 
            pre.next = null;

        slow = reverse(slow);
        merge(head, slow);
    }
    ListNode reverse(ListNode head){
        ListNode pre = null;
        while(head != null){
            ListNode tmp = head.next;
            head.next = pre;
            pre = head;
            head = tmp;
        }
        return pre;
    }
    void merge(ListNode l1, ListNode l2){
        while(l1 != null && l2 != null){
            ListNode tmp1 = l1.next;
            ListNode tmp2 = l2.next;
            l1.next = l2;
            l2.next = tmp1;
            l1 = tmp1;
            l2 = tmp2;
        }
    }

82. 删除排序链表中的重复元素 II

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中没有重复出现的数字。

示例 1:

输入: 1->2->3->3->4->4->5

输出: 1->2->5

示例 2:

输入: 1->1->1->2->3

输出: 2->3

思路：建立虚拟头结点pre，依次遍历链表，若pre.next.val == pre.next.next.val，则证明出现了重复节点，此时只要在pre.next.next之后找到node.val != pre.next.val的节点，再将pre.next = val即可跳过所有重复节点。

    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
        while(cur.next != null && cur.next.next != null){
            ListNode tmp = cur.next;
            if(tmp.val == tmp.next.val)
                while(tmp != null && tmp.next != null && tmp.val == tmp.next.val)
                    tmp = tmp.next;
                cur.next = tmp.next;
            else
                cur = cur.next;
        }
        return dummy.next;
    }

725. 分隔链表

给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1，也就是说可能有些部分为 null。

这k个部分应该按照在链表中出现的顺序进行输出，并且排在前面的部分的长度应该大于或等于后面的长度。

返回一个符合上述规则的链表的列表。

举例： 1->2->3->4, k = 5 // 5 结果 [ [1], [2], [3], [4], null ]

示例 1：

输入: root = [1, 2, 3], k = 5

输出: [[1],[2],[3],[],[]] 解释:输入输出各部分都应该是链表，而不是数组。

例如, 输入的结点 root 的 val= 1, root.next.val = 2, \root.next.next.val = 3, 且 root.next.next.next = null。

第一个输出 output[0] 是 output[0].val = 1, output[0].next = null。

最后一个元素 output[4] 为 null, 它代表了最后一个部分为空链表。

示例 2：

输入: root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3

输出: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]

解释:

输入被分成了几个连续的部分，并且每部分的长度相差不超过1.前面部分的长度大于等于后面部分的长度。

思路：这道题当时想了很久，总结关键点如下：

统计链表的长度count，则每个部分应该含有count / k 个节点，如假设count = 11，k = 3，那么每部分应该含有11 / 3 = 3(向下取整)个节点，剩下的 11 - 3 * 3 = 2 个节点代表前2个分段应该多包含1个节点

以下代码是我纯手打，一遍AC的，太爽了！

    public ListNode[] splitListToParts(ListNode root, int k) {
        ListNode[] res = new ListNode[k];
        ListNode cur = root;
        int cunt = 0;
        while(cur != null){
            cur = cur.next;
            cunt ++;
        }
        int block = cunt / k;
        int carry = cunt % k;
        cur = root;
        int pos = 0;
        while(cur != null){
            int size = block + (carry-- > 0 ? 1 : 0);
            ListNode tmp = cur;
            for(int i = 0; i < size - 1 && cur.next != null; ++i){
                cur = cur.next;
            }
            ListNode nxt = cur.next;
            cur.next = null;
            cur = nxt;
            res[pos++] = tmp;
        }
        return res;
    }

142. 环形链表 II

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

进阶：

你是否可以使用 O(1) 空间解决此题？

示例 1：

输入：head = [3,2,0,-4], pos = 1

输出：返回索引为 1 的链表节点

解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0

输出：返回索引为 0 的链表节点

解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1

输出：返回 null

解释：链表中没有环。

提示：

链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引

思路：我也不知道这道题为啥能当Medium，我感觉和Eazy毫无区别。

    public ListNode detectCycle(ListNode head) {
        ListNode cur = head;
        while(cur != null){
            if(cur.val == Integer.MAX_VALUE)
                return cur;
            cur.val = Integer.MAX_VALUE;
            cur = cur.next;
        }
        return null;
    }

328. 奇偶链表

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例 1:

输入: 1->2->3->4->5->NULL

输出: 1->3->5->2->4->NULL

示例 2:

输入: 2->1->3->5->6->4->7->NULL

输出: 2->3->6->7->1->5->4->NULL

说明:

应当保持奇数节点和偶数节点的相对顺序。
链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

思路：这道题最开始的思路是先遍历完所有的奇数节点，再遍历偶数节点，最后进行拼接，可后来发现，当所有的奇数节点的指针都指向下一个奇数节点时，已经无法对偶数节点进行遍历（因为前驱结点已经消失，相当于把偶数节点删除了）。后来经过研究，发现可以同时遍历奇数节点和偶数节点，问题解决，以下代码一遍AC。

    public ListNode oddEvenList(ListNode head) {
        if(head == null) return head;
        ListNode oddHead = head, evenHead = head.next;
        ListNode oddCur = oddHead, evenCur = evenHead;
        while(oddCur != null && evenCur != null && evenCur.next != null){
            oddCur.next = oddCur.next.next;
            evenCur.next = evenCur.next.next;
            oddCur = oddCur.next;
            evenCur = evenCur.next;
        }
        oddCur.next = evenHead;
        return oddHead;
    }

面试题 02.04. 分割链表

编写程序以 x 为基准分割链表，使得所有小于 x 的节点排在大于或等于 x 的节点之前。如果链表中包含 x，x 只需出现在小于 x 的元素之后(如下所示)。分割元素 x 只需处于“右半部分”即可，其不需要被置于左右两部分之间。

示例:

输入: head = 3->5->8->5->10->2->1, x = 5

输出: 3->1->2->10->5->5->8

思路：由于链表中的节点是无序的，所以原地排序的难度很高，暂时想不出解决方案。所以目前的思路是new两个头结点，将node.val < x的节点放在head1后，将node.val >= x的节点放在head2后，最后再将head2和head1连接起来即可。

哭了哭了哭了，有感觉了，有感觉了，这道题又是1遍AC100%，酬勤酬勤。

    public ListNode partition(ListNode head, int x) {
        ListNode bigHead = new ListNode(0);
        ListNode smallHead = new ListNode(0);
        ListNode bigCur = bigHead, smallCur = smallHead;
        while(head != null){
            if(head.val < x){
                smallCur.next = head;
                smallCur = smallCur.next;
            } else {
                bigCur.next = head;
                bigCur = bigCur.next;
            }
            head = head.next;
        }
        smallCur.next = bigHead.next;
        bigCur.next = null;
        return smallHead.next;
    }

1019. 链表中的下一个更大节点

给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为：node_1, node_2, node_3, … 。

每个节点都可能有下一个更大值（next larger value）：对于 node_i，如果其 next_larger(node_i) 是 node_j.val，那么就有 j > i 且 node_j.val > node_i.val，而 j 是可能的选项中最小的那个。如果不存在这样的 j，那么下一个更大值为 0 。

返回整数答案数组 answer，其中 answer[i] = next_larger(node_{i+1}) 。

注意：在下面的示例中，诸如 [2,1,5] 这样的输入（不是输出）是链表的序列化表示，其头节点的值为 2，第二个节点值为 1，第三个节点值为 5 。

示例 1：

输入：[2,1,5]

输出：[5,5,0]

示例 2：

输入：[2,7,4,3,5]

输出：[7,0,5,5,0]

示例 3：

输入：[1,7,5,1,9,2,5,1]

输出：[7,9,9,9,0,5,0,0]

提示：

对于链表中的每个节点，1 <= node.val <= 10^9
给定列表的长度在 [0, 10000] 范围内

思路：感觉这题除了暴力想不出其他的办法，但是暴力算法的代码不够优雅，所以就先放在这里吧，日后想到其他的办法再来填坑。（看了题解貌似用单调栈可以解决，最近2道题都用了单调栈，感觉自己掌握的不是很好，等刷完了树就来啃这块骨头）

92. 反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明: 1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4

输出: 1->4->3->2->5->NULL

思路：不多说了， E A Z Y 就完事儿了。(我开玩笑的，这题挺难的，我一开始看错题了)

    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dmy = new ListNode(0);
        dmy.next = head;
        int delta = n-m;
        ListNode pre = dmy,tail = head;
        //先定位出m节点和m之前的节点
        while(m>1){
            pre = tail;
            tail = tail.next;
            m--;
        }
        while(delta > 0){
            ListNode next = tail.next;
            tail.next = next.next;//tail一直不变，只要修改指针到next.next
            next.next = pre.next;//next.next指向pre的next，也就是最新的第m个位置
            pre.next = next;//更新next为最新的第m个位置
            delta --;
        }
        return dmy.next;
    }

19. 删除链表的倒数第N个节点

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

示例：

定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

思路：first节点先走n步，second节点设为head，之后同时= *.next即可。

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = head;
        ListNode second = dummy;
        for (int i = 0; i < n; ++i)
            first = first.next;
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }

1171. 从链表中删去总和值为零的连续节点

给你一个链表的头节点 head，请你编写代码，反复删去链表中由总和值为 0 的连续节点组成的序列，直到不存在这样的序列为止。

删除完毕后，请你返回最终结果链表的头节点。

你可以返回任何满足题目要求的答案。

（注意，下面示例中的所有序列，都是对 ListNode 对象序列化的表示。）

示例 1：

输入：head = [1,2,-3,3,1]

输出：[3,1]

提示：答案 [1,2,1] 也是正确的。

示例 2：

输入：head = [1,2,3,-3,4]

输出：[1,2,4]

示例 3：

输入：head = [1,2,3,-3,-2]

输出：[1]

思路：用一个map保存所有前项的和 and 链表节点。遍历节点，若当前和 and map中保存的 sum 不同，则该节点的 next 指向 map中的节点。

    public ListNode removeZeroSumSublists(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        Map<Integer, ListNode> map = new HashMap<>();
        int sum = 0;
        for (ListNode d = dummy; d != null; d = d.next) {
            sum += d.val;
            map.put(sum, d);
        }
        sum = 0;
        for (ListNode d = dummy; d != null; d = d.next) {
            sum += d.val;
            d.next = map.get(sum).next;
        }
        return dummy.next;
    }

总结

原本想都写完的，但今天是在是太累了，有时间再写Medium吧~。在写这篇文章的过程中，重新将链表的Eazy题目做了一遍，这个过程明显比一周前要顺利的多，很多道题用了比之前更加优雅的代码，也算有了成长。

If you are not proud of it , it’s not enough.

More Details：Setting up your GitHub Pages site locally with Jekyll

难度：Eazy

面试题 02.02. 返回倒数第 k 个节点

面试题 02.03. 删除中间节点

21. 合并两个有序链表

234. 回文链表

剑指 Offer 18. 删除链表的节点

876. 链表的中间结点

203. 移除链表元素

剑指 Offer 52. 两个链表的第一个公共节点

『优 雅 警 告 ！』

206. 反转链表

1290. 二进制链表转整数

141. 环形链表

面试题 02.01. 移除重复节点

1474. 删除链表 M 个节点之后的 N 个节点

难度：Medium

61. 旋转链表

369. 给单链表加一

445. 两数相加 II

24. 两两交换链表中的节点

143. 重排链表

82. 删除排序链表中的重复元素 II

725. 分隔链表

142. 环形链表 II

328. 奇偶链表

面试题 02.04. 分割链表

1019. 链表中的下一个更大节点

92. 反转链表 II

19. 删除链表的倒数第N个节点

1171. 从链表中删去总和值为零的连续节点

总结

『优雅警告！』