7、链表

重点学习
奇偶链表、两两交换链表中的节点、排序链表、删除链表的倒数第N个节点、回文链表

206. 反转链表

题解思路1：迭代

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
         ListNode pre=null;    //前指针节点
        ListNode cur=head;  //当前指针节点
        while(cur!=null){ 
            ListNode next=cur.next;//临时节点，暂存当前节点的下一个节点的信息，用于后移
            cur.next=pre;//将当前节点指向它前面的节点
            pre=cur;     //前指针后移
            cur=next；   //当前指针后移
         }
        return pre;
   }

题解思路2：递归

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head.next==null)  return head;
        ListNode newHead=reverseList(head.next);
        head.next.next=head;
        head.next=null;
        return newHead;
    }
}

注：考虑递归问题最重要的一个点就是不要跳入到递归的过程里面去，在自己的脑中不断的压栈出栈。这样只会把问题想的更加的复杂。我们应该具体到一个点中，去想在当前点的时候要怎么去做，去完成。剩余的点也按着一样的逻辑思路去操作就好。

92. 反转链表 II

方法1：双指针-头插法
思路：
1、定义两个指针，分别称为g（guard守卫）和p（point）。
根据方法的参数m确定g和p的位置，将g移动到第一个要反转的节点的前面，将p移动到第一个要反转的节点的位置

2、将p后面的元素删除，然后添加到g的后面，也即是头插法

3、重复步骤2(n-m次)
4、返回dummyHead.next

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dummyHead=new ListNode(0);
        dummyHead.next=head;
        ListNode g=dummyHead;
        ListNode p=dummyHead.next;
        int index=0;
        while(index<m-1){
            g=g.next;
            p=p.next;
            index++;
        }
        for(int i=0;i<n-m;i++){
            ListNode removed=p.next;
            p.next=p.next.next;
            removed.next=g.next;
            g.next=removed;
        }
        return dummyHead.next;
    }
}

• 方法2：题206的思路

  class Solution {
     public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode superior = dummyHead;
        // 1. 遍历至m的前一个节点
        for ( int i = 1; i < m; i ++ ) {
            superior = superior.next;
        }
        ListNode prev = null;
        ListNode cur = superior.next;
        // 2. 180°旋转
        for ( int i = 0; i <= n-m; i ++ ) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
         // 3. 修改m和n-m位置处的节点的指向
        superior.next.next = cur;
        superior.next = prev;
        return dummyHead.next;
    }
  }

  

  跳出循环时，指针的样子

• 方法3：递归

  class Solution {
    ListNode successor=null;
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(left==1)
            return reverseN(head,right);
        head.next=reverseBetween(head.next,left-1,right-1);
        return head;
    }
    ListNode reverseN(ListNode head, int n) {
        if (n == 1) { 
            // 记录第 n + 1 个节点
            successor = head.next;
            return head;
        }
        // 以 head.next 为起点，需要反转前 n - 1 个节点
        ListNode last = reverseN(head.next, n - 1);
        head.next.next = head;
        // 让反转之后的 head 节点和后面的节点连起来
        head.next = successor;
        return last;
    }    
  }

  注：在考虑这个问题的过程中，不断深入考虑一下几个点。
  1、单纯的反转链表的思路（题207）
  2、控制前n个节点反转的思路
  3、起始位置不是在第一个节点的思路

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

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode pre =new ListNode(-1);
        ListNode cur=head;
        while(cur!=null){
            if(pre.val==cur.val){
                cur=cur.next;
                pre.next=cur;
            }else{
                 pre.next=cur;
                 pre=cur;
                 cur=cur.next;
            }
        }
        return head;
    }
}

注：1、如果存在相同的元素就移动当前指针，改变上一个指针的指向
2、如果下一个指针与上一个指针是不一样的话，那么就更新上一个指针的指向，然后修改上一个指针以及当前指针的位置。

官方操作答案

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode current = head;
        while(current!=null&&current.next!=null){
            if(current.next.val==current.val){
                current.next=current.next.next;
            }else{
                current=current.next;
            }
        }
        return head;
    }
}

注：判断当前节点的值是否等于下一个节点的值，相等的话将当前值指向下下个节点

86. 分隔链表

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode before=new ListNode(0);
        ListNode after=new ListNode(0);
        ListNode headBefore=before;//哑节点，保存头元素
        ListNode headAfte=after;//哑节点，保存头元素
        ListNode cur=head;
        while(cur!=null){
            if(cur.val<x){
                before.next=cur;
                before=before.next;
            }else{
                after.next=cur;
                after=after.next;
            }
            cur=cur.next;
        }
        after.next=null;//解决循环指针的出现，取消大于x的元素中最后一个元素的指向
        before.next=headAfte.next;
        return headBefore.next;
    }
}

注意点： 1.创建哑节点来保存头元素的信息 2.最后一个大于x的元素指向置为null，避免循环指针的出现

328. 奇偶链表

方法一：分离节点后合并

如果链表为空，则直接返回链表。

• 对于原始链表，每个节点都是奇数节点或偶数节点。头节点是奇数节点，头节点的后一个节点是偶数节点，相邻节点的奇偶性不同。因此可以将奇数节点和偶数节点分离成奇数链表和偶数链表，然后将偶数链表连接在奇数链表之后，合并后的链表即为结果链表。
• 原始链表的头节点 head 也是奇数链表的头节点以及结果链表的头节点，head 的后一个节点是偶数链表的头节点。令 evenHead = head.next，则 evenHead 是偶数链表的头节点。
• 维护两个指针 odd 和 even 分别指向奇数节点和偶数节点，初始时 odd = head，even = evenHead。通过迭代的方式将奇数节点和偶数节点分离成两个链表，每一步首先更新奇数节点，然后更新偶数节点。
• 更新奇数节点时，奇数节点的后一个节点需要指向偶数节点的后一个节点，因此令 odd.next = even.next，然后令 odd = odd.next，此时 odd 变成 even 的后一个节点。
• 更新偶数节点时，偶数节点的后一个节点需要指向奇数节点的后一个节点，因此令 even.next = odd.next，然后令 even = even.next，此时 even 变成 odd 的后一个节点。

  在上述操作之后，即完成了对一个奇数节点和一个偶数节点的分离。重复上述操作，直到全部节点分离完毕。全部节点分离完毕的条件是 even 为空节点或者 even.next 为空节点，此时 odd 指向最后一个奇数节点（即奇数链表的最后一个节点）。 最后令 odd.next = evenHead，将偶数链表连接在奇数链表之后，即完成了奇数链表和偶数链表的合并，结果链表的头节点仍然是 head。

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode evenHead = head.next;
        ListNode odd = head, even = evenHead;
        while (even != null && even.next != null) {//importment(无论节点个数是奇或偶都满足这个条件)
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
}

注意点：在判断条件中，使用了even.next!=null的条件，是为了保证偶数链表一定走到了最后

2. 两数相加

题解思路： 1、审查题目，各自位数是按照逆序的方式存储的，那么从头元素开始相加正好对应着数学中的从低位开始处理 2、注意点：是否存在进位操作、两条链表对应的数据位数是不是相等的

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
       ListNode root=new ListNode(0);
       ListNode cur=root;
       int carry=0;//进位值  
       int sumNum=0;
       while(l1!=null||l2!=null||carry!=0){
           int l1Val=l1!=null?l1.val:0;
           int l2Val=l2!=null?l2.val:0;
           sumNum=l1Val+l2Val+carry;
           carry=sumNum/10;
           cur.next=new ListNode(sumNum%10);
           cur=cur.next;
           if(l1!=null) l1=l1.next;
           if(l2!=null) l2=l2.next;
       }
       return root.next;
    }
}

要想清楚一个关系，这里的逆序其实就是方便我们从低位开始计算，只要处理好进位的逻辑就可以了

445. 两数相加 II

题解思路： 1、先将链表进行反转，思路参考206 2、将两条链表进行相加，思路参考2

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode n1=reverse(l1);
        ListNode n2=reverse(l2);

        ListNode root=new ListNode(0);
        ListNode cur=root;
        int carry=0;
        int sumNum=0;

        while(n1!=null||n2!=null||carry!=0){
            int n1Val=n1!=null?n1.val:0;
            int n2Val=n2!=null?n2.val:0;
            sumNum=n1Val+n2Val+carry;

            carry=sumNum/10;

            cur.next=new ListNode(sumNum%10);
            cur=cur.next;

            if(n1!=null) n1=n1.next;
            if(n2!=null) n2=n2.next;

        }

        ListNode res=reverse(root.next);
        return res;   
    }

    private ListNode reverse(ListNode head){
        ListNode pre=null;
        ListNode cur=head;

        while(cur!=null){
            ListNode next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
}

方法二：使用堆来实现链表元素的反序

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> stack1=new Stack<>();
        Stack<Integer> stack2=new Stack<>();
        while(l1!=null){
            stack1.push(l1.val);
            l1=l1.next;
        }
        while(l2!=null){
            stack2.push(l2.val);
            l2=l2.next;
        }
        int carry=0;
        int sum=0;
        ListNode root=null;
        while(!stack1.isEmpty()||!stack2.isEmpty()||carry!=0){
            int stack1Val=stack1.isEmpty()?0:stack1.pop();
            int stack2Val=stack2.isEmpty()?0:stack2.pop();
            sum=carry+stack1Val+stack2Val;

            carry=sum/10;
            ListNode node=new ListNode(sum%10);
            node.next=root;
            root=node;

        }
        return root;
    }
}

注意stack 的方法stack.isempty() ，stack.pop()，stack.push();

203. 移除链表元素

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

创建虚拟表头，虚拟表头的下一个节点为head节点，创建当前节点等于虚拟表头节点 cur.next

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

方法一：删除所有头部的重复节点，返回不重复的第一个节点（递归）
1、特殊情况：头节点为null或头节点下一个节点为null，直接返回头节点，这时不存在重复节点
2、如果头节点与头节点的下一个节点值相等，就跳过所有的相等节点。递归调用函数判断最后一个跳过节点的后一个节点。
3、如果头节点与头节点的下一个节点值不等，递归调用函数判断头节点的后一个节点。

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        if (head.val == head.next.val) {
            while (head != null && head.next != null && head.val == head.next.val) {
                head = head.next;
            }
            return deleteDuplicates(head.next);
        } else {
            head.next = deleteDuplicates(head.next);
            return head;
        }
    }
}

方法二：map+创建新链表（map用于记录出现的次数）

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        //用哈希表记录每个节点值出现的频率
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        List<Integer> arr = new ArrayList<>();
        ListNode p = head;
        while (p != null) {
            int val = p.val;
            if (map.containsKey(val)) {
                map.put(val, map.get(val) + 1);
            } else {
                map.put(val, 1);
            }
            p = p.next;
        }
        //将只出现一次的值放到arr中，之后再对这个arr排序
        for (Integer k : map.keySet()) {
            if (map.get(k) == 1) {
                arr.add(k);
            }
        }
        Collections.sort(arr);
        ListNode dummy = new ListNode(-1);
        p = dummy;
        //创建长度为arr.length长度的链表,依次将arr中的值赋给每一个链表节点
        for (Integer i : arr) {
            ListNode temp = new ListNode(i);
            p.next = temp;
            p = p.next;
        }
        return dummy.next;
    }
}

方法三：
思路：
初始两个指针：将a指针指向哑节点，将b指针指向head（哑节点的下一个节点）
1、如果a指向的值不等于 b指定的值，则两个指针都前进一位
2、否则就单独移动b，b不断往前走，知道a指向的值不等于b指向的值
注意：这里不是直接比较a.val==b.val，这样比较是不对的，因为初始化的时候，a指向的是哑节点，所以比较逻辑应该是

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode a = dummy;
        ListNode b = head;

        while (b != null && b.next!= null) {
            //初始化时a指向的值为哑节点，所以比较的逻辑应该是a的下一个节点和b的下一个节点
            if (a.next.val != b.next.val) {
                a = a.next;
                b = b.next;
            } else {
                //如果b和a指向的节点是相等的。就不断的移动b，知道b的下一个节点的值不等于为止
                while (b != null && b.next != null && a.next.val == b.next.val) {
                    b = b.next;
                }
                a.next = b.next;
                b =  b.next;
            }
        }
        return dummy.next;
    }
}

自己一开始的思路就是a.val=b.val这样的做法无法满足特殊情况

方法四
思路：
1、与方法三思路类似，初始化b指针指向head.next
2、判断两个指针指向的节点数是否相等是条件为a.next.val==b.val

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode a = dummy;
        ListNode b = head.next;

        while (b != null) {
            if (a.next.val == b.val) {
                while (b != null && a.next.val == b.val) {
                    b = b.next;
                }
                a.next = b;
                b = (b == null) ? null : b.next;
            } else {
                a = a.next;
                b = b.next;
            }
        }
        return dummy.next;
    }
}

边界条件的处理尤为重要

21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
方法一：暴力解法

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 == null ? l2 : l1;
        return dummy.next;
    }
}

注意点： 1、while循环退出的条件 2、处理剩余的链表

方法二：递归
思路：
我们可以如下递归的定义两个链表里的merge操作（忽略边界情况，比如空链表等）：
第一种情况：list1[0]+merge(list[1],list2) list1[0]第二种情况：list2[0]+merge(list1,list2[1]) othersize

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null){
            return l2;
        }else if (l2==null){
            return l1;
        }else if (l1.val<l2.val){
            l1.next=mergeTwoLists(l1.next,l2);
            return l1;
        }else{
            l2.next=mergeTwoLists(l1,l2.next);
            return l2;
        }
    }
}

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

方式一：两两节点交换

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyNode=new ListNode(-1);
        dummyNode.next=head;

        ListNode pre=dummyNode;
        while(pre.next!=null&&pre.next.next!=null){
            ListNode node1=pre.next;
            ListNode node2=pre.next.next;

            node1.next=node2.next;
            node2.next=node1;
            pre.next=node2;

            pre=node1;        //注意此时node1已经来到了node2的位置
        }
        return dummyNode.next;
    }
}

方式二：递归（妙）

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }

        ListNode newHead=head.next;
        head.next=swapPairs(newHead.next);
        newHead.next=head;
        return newHead;
    }
}

25. K 个一组翻转链表

方法一：
思路：
步骤分解:
1、链表分区为已翻转部分+待翻转部分+未翻转部分
2、每次翻转前，要确定翻转链表的范围，这个必须通过 k 此循环来确定
3、需记录翻转链表前驱和后继，方便翻转完成后把已翻转部分和未翻转部分连接起来
4、初始需要两个变量 pre 和 end，pre 代表待翻转链表的前驱，end 代表待翻转链表的末尾
5、经过k此循环，end 到达末尾，记录待翻转链表的后继 next = end.next
6、翻转链表，然后将三部分链表连接起来，然后重置 pre 和 end 指针，然后进入下一次循环
7、特殊情况，当翻转部分长度不足 k 时，在定位 end 完成后，end==null，已经到达末尾，说明题目已完成，直接返回即可
8、时间复杂度为 O(n*K)O(n∗K) 最好的情况为 O(n)O(n) 最差的情况未 O(n^2)
9、空间复杂度为 O(1)O(1) 除了几个必须的节点指针外，我们并没有占用其他空间

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
      ListNode dummy=new ListNode(0);
      dummy.next=head;
      ListNode pre=dummy;
      ListNode end=dummy;

      while(end!=null){
          for(int i=0;i<k&&end!=null;i++){
            end=end.next;
          }
          if (end==null) break;

          ListNode start=pre.next;
          ListNode next=end.next;
          end.next=null;
          pre.next=reverse(start);
          start.next=next;
          pre=start;
      }

      return dummy.next;
    }

    private ListNode reverse(ListNode head){
        ListNode pre=null;
        ListNode cur=head;
        while(cur!=null){
            ListNode nextNode=cur.next;
            cur.next=pre;
            pre=cur;
            cur=nextNode;
        }
        return pre;
    }
}

方法二：递归（TODO）
解题步骤
1、找到待翻转的k个节点（注意：若剩余数量小于 k 的话，则不需要反转，因此直接返回待翻转部分的头结点即可）。
2、对其进行翻转。并返回翻转后的头结点（注意：翻转为左闭右开区间，所以本轮操作的尾结点其实就是下一轮操作的头结点）。
3、对下一轮 k 个节点也进行翻转操作。
4、将上一轮翻转后的尾结点指向下一轮翻转后的头节点，即将每一轮翻转的k的节点连接起来。

  public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode tail = head;
        for (int i = 0; i < k; i++) {
            //剩余数量小于k的话，则不需要反转。
            if (tail == null) {
                return head;
            }
            tail = tail.next;
        }
        // 反转前 k 个元素
        ListNode newHead = reverse(head, tail);
        //下一轮的开始的地方就是tail
        head.next = reverseKGroup(tail, k);

        return newHead;
    }

    /*
    左闭右开区间
     */
    private ListNode reverse(ListNode head, ListNode tail) {
        ListNode pre = null;
        ListNode next = null;
        while (head != tail) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;

    }

147. 对链表进行插入排序

class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return head;
        }

        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode lastSorted = head;
        ListNode curr = head.next;

        while (curr != null) {
            if (lastSorted.val < curr.val) {
                lastSorted = lastSorted.next;
            } else {
                ListNode prev = dummyHead;
                while (prev.next.val <= curr.val) {
                    prev = prev.next;
                }
                lastSorted.next=curr.next;
                curr.next=prev.next;
                prev.next=curr;
            }
            curr=lastSorted.next;
        }
        return dummyHead.next;
    }
}

prev、lastsorted、curr三者之间的关系

237. 删除链表中的节点

方法：改变节点的值，因为传入的参数只有要删除的节点，而没有给出整个链表的信息，所以无法通过获取前一节点的方式删除

class Solution {
    public void deleteNode(ListNode node) {
        if(node==null){//判断
            return;
        }
        if(node.next==null){//边界条件的判断
            node=null;
            return;
        }
        node.val=node.next.val;
        ListNode delNode=node.next;
        node.next=delNode.next;
        delNode.next=null;
    }
}

148. 排序链表

| 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
进阶：
- 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

示例 1：

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

题目进阶要求时间复杂度为O（nlogn），其中
能达到这个时间复杂度的排序算法有归并排序、堆排序和快速排序
其中最适合链表的排序算法是归并排序。

归并排序基于分治算法。最容易想到的实现方式是自顶向下的递归实现，考虑到递归调用的栈空间，自顶向下归并排序的空间复杂度是 O(logn)。如果要达到 O(1) 的空间复杂度，则需要使用自底向上的实现方式。

方法1：自顶向下归并排序
对链表自顶向下归并排序的过程如下。
1、找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 2 步，慢指针每次移动 1 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。
2、对两个子链表分别排序。
3、将两个排序后的子链表合并，得到完整的排序后的链表。可以使用「21. 合并两个有序链表」的做法，将两个有序的子链表进行合并。

上述过程可以通过递归实现。递归的终止条件是链表的节点个数小于或等于 1，即当链表为空或者链表只包含 1 个节点时，不需要对链表进行拆分和排序。

class Solution {
    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;                    ***
        }
        ListNode head2 = slow.next;
        slow.next = null;
        return merge(sortList(head), sortList(head2));
    }

    public ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(-1);
        ListNode tem = dummy, tem1 = head1, tem2 = head2;
        while (tem1 != null && tem2 != null) {
            if (tem1.val > tem2.val) {
                tem.next = tem2;
                tem2 = tem2.next;
            } else {
                tem.next = tem1;
                tem1 = tem1.next;
            }
            tem = tem.next;
        }
        if (tem1 != null) {
            tem.next = tem1;
        }
        if (tem2 != null) {
            tem.next = tem2;
        }
        return dummy.next;
    }
}

注：在正常的寻找链表的中点的题目中，标记处的写法是fast=head。但是这里写的是fast=head.next。解决的是当链表只有两个值无法跳出循环的问题。

方法二：自底向上归并排序
使用自底向上的方法实现归并排序，则可以达到 O(1)O(1) 的空间复杂度。

25. K 个一组翻转链表

| 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
进阶：
- 你可以设计一个只使用常数额外空间的算法来解决此问题吗？
- 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5] | | —- |

题解思路：首先审题可知这题的要求是反转链表，我们可以把每K个节点作为一个大节点来处理。结合206题的递归做法

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head==null)  return null;
        ListNode a=head;
        ListNode b=head;
        for(int i=0;i<k;i++){
            if(b==null) return a;
            b=b.next;
        }
        ListNode newHead=reverse(a,b);
        a.next=reverseKGroup(b,k);
        return newHead;
    }

    public ListNode reverse(ListNode a,ListNode b){
        ListNode pre=null;
        ListNode next=null;
        while(a!=b){
            next=a.next;
            a.next=pre;
            pre=a;
            a=next;
        }
        return pre;
    }
}

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

题解思路1：双指针，之间包含的节点的个数为题目所给出的节点数。这样可以正好保证q指针走到null值时，p指针为待删除节点的前一个节点

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyNode=new ListNode(-1);
        dummyNode.next=head;
        ListNode p=dummyNode;
        ListNode q=dummyNode;

        for(int i=0;i<n+1;i++){
            q=q.next;
        }

        while(q!=null){
            q=q.next;
            p=p.next;
        }

        ListNode delNode=p.next;
        p.next=delNode.next;
        delNode.next=null;

        return dummyNode.next;
    }
}

模式识别：

• 涉及链表的特殊位置，考虑快慢指针
• 要删除链表节点，找到它的前驱

题解思路2：遍历链表得出链表的总长度L，删除从列表开头数起的（L-n+1）个节点

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyNode=new ListNode(-1);
        dummyNode.next=head;
        ListNode p=dummyNode;
        int sum=0;//链表的总长度

        while(p.next!=null){
            p=p.next;
            sum++;
        }

        p=dummyNode;
        for(int i=0;i<sum-n;i++){
            p=p.next;
        }

        ListNode delNode=p.next;
        p.next=delNode.next;

        return dummyNode.next;
    }
}

61. 旋转链表

自己的解题思路：

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        ListNode dummyHead=new ListNode(-1);
        dummyHead.next=head;
        ListNode p=dummyHead;
        ListNode q=dummyHead;

        for(int i=0;i<k;i++){
            q=q.next;
        }

        while(q.next!=null){
            q=q.next;
            p=p.next;
        }

        ListNode newHead=p.next;
        p.next=null;

        q.next=head;

        return newHead;
    }
}

当k的值大于链表的长度时，这种做法是无法得到正确的结果的。

题解思路1：将链表闭合成环，找到相应的位置，确定新的链表头和链表尾

关键点：新的链表头在哪里？ 在位置 **n-k** 处，其中 **n** 是链表中点的个数，新的链表尾就在头的前面，位于位置 **n-k-1**。

class Solution {
  public ListNode rotateRight(ListNode head, int k) {
    if (head == null) return null;
    if (head.next == null) return head;

    ListNode old_tail = head;
    int n;
    for(n = 1; old_tail.next != null; n++)
      old_tail = old_tail.next;
    old_tail.next = head;

    // find new tail : (n - k % n - 1)th node
    // and new head : (n - k % n)th node
    ListNode new_tail = head;
    for (int i = 0; i < n - k % n - 1; i++)
      new_tail = new_tail.next;
    ListNode new_head = new_tail.next;

    // break the ring
    new_tail.next = null;

    return new_head;
  }
}

关键点，新的尾节点出现在哪里？ （ n - k % n - 1）

143. 重排链表

题解思路1：利用线性表存储该链表，然后利用线性表可以访问下标的特点，直接按顺序访问指定元素，重建该链表即可

class Solution {
    public void reorderList(ListNode head) {
        if (head == null)
            return ;
        List<ListNode> list = new ArrayList<>();
        ListNode node = head;
        while (node != null) {
            list.add(node);
            node = node.next;
        }

        int i = 0, j = list.size() - 1;
        while (i < j) {
            list.get(i).next = list.get(j);
            i++;
            if (i == j)
                break;
            list.get(j).next=list.get(i);
            j--;
        }
        list.get(i).next=null;
    }
}

注意点：while循环内进行了两次next操作

题解思路2：寻找中间节点+链表逆序+合并链表

• 寻找中间节点：876、使用快慢指针来实现
• 链表逆序：206、迭代法实现

• 链表合并：使用中间变量存储节点

  class Solution {
    public void reorderList(ListNode head) {
        if (head == null)
            return;
        ListNode mid = middleNode(head);
        ListNode l1 = head;
        ListNode l2 = mid.next;
        mid.next = null;
        l2 = resverList(l2);
        mergeList(l1, l2);
    }
  
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
  
        while(fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;//这个就是中间节点，快的走两步，慢的走一步
    }
  
    public ListNode resverList(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }
  
    public void mergeList(ListNode l1, ListNode l2) {
        ListNode l1_tem;
        ListNode l2_tem;
  
        while (l1 != null && l2 != null) {
            l1_tem = l1.next;
            l2_tem = l2.next;
  
            l1.next = l2;
            l1 = l1_tem;
  
            l2.next = l1;
            l2 = l2_tem;
        }
    }
  }
  

234. 回文链表

题解思路1：参考题143的方案解决

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head==null)
            return true;
        if (head.next==null)
            return true;
        ListNode middle = middleNode(head);
        ListNode l1 = head;
        ListNode l2 = middle.next;
        middle.next = null;

        l2 = resverse(l2);

        return checkPalindrome(l1, l2);
    }

    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public ListNode resverse(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }

    public boolean checkPalindrome(ListNode l1, ListNode l2) {
        while (l1 != null && l2 != null) {
            if (l1.val != l2.val) {
                return false;
            } else {
                l1 = l1.next;
                l2 = l2.next;
            }
        }
        return true;
    }
}

题解思路2：使用数组存储链表的数据，再使用双链表的方式实行

class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> list = new ArrayList<>();
        ListNode curr = head;
        //通过循环将链表的数值全部存储到链表中
        while (curr != null) {
            list.add(curr.val);
            curr = curr.next;
        }

        //直接在list链表上使用双指针进行判断
        int p = 0;
        int q = list.size() - 1;
        while (p < q) {
            if (list.get(p) != list.get(q))
                return false;
            else {
                p++;
                q--;
            }
        }
        return true;
    }
}

时间复杂度：O(n) 空间复杂度：O(n)

题解思路3：递归法(难顶)

class Solution {
    private ListNode frontPointer;

    private boolean recursivelyCheck(ListNode currentNode) {
        if (currentNode != null) {
            if (!recursivelyCheck(currentNode.next)) {
                return false;
            }
            if (currentNode.val != frontPointer.val) {
                return false;
            }
            frontPointer = frontPointer.next;
        }
        return true;
    }


    public boolean isPalindrome(ListNode head) {
        frontPointer = head;
        return recursivelyCheck(head);
    }