反转链表

问题1

如何把一个链表反转过来，例如1->2->3->4 反转为4->3->2->1 ?

原理

可以重写定义一个头结点，然后采用头插的方式把老的链表插入到新的链表里，头插法如何实现可以参考：头插法

代码

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode newHead = new ListNode(-1);
        ListNode run = newHead;
        while (head!=null){
            ListNode cur = head;
            head = head.next;
            cur.next = run.next;
            run.next = cur;
        }
        return newHead.next;
    }
}

注意事项

在做头插的时候要注意节点移动的时候，ListNode cur = head; head = head.next; 不要让老的链表断开。

问题2

如何旋转链表的m->n中间节点旋转过来，例如1->2->3->4 反转2到3为 1->3->2->4

原理

• 首先，找到第m个节点的前一个节点记录下来，第m个节点也要保存下来，这个记录为第一部分节点。
• 其次，用头插法把m到n之间的节点反转，记录为第二部分节点，剩余的节点为第三部分节点。
• 最后，把第一部分节点和第二部分节点连起来，同时把第m个节点和剩余的第三部分节点连接起来。

代码

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head==null){
            return head;
        }
        // find first
        ListNode newHead = new ListNode(-1);
        ListNode run = newHead;
        for(int i=1;i<m;i++){
            run.next = head;
            head = head.next;
            run = run.next;
        }
            
        // find second
        ListNode dump = head;
        ListNode reverseHead = new ListNode(-1);
        ListNode reverseRun = reverseHead;
        for(int i=m;i<=n;i++){
            ListNode cur = head;
            head = head.next;
            cur.next = reverseRun.next;
            reverseRun.next = cur;
        }
        //find third
        run.next = reverseHead.next;
        dump.next = head;

        return newHead.next;
    }
}

注意事项

• 在做头插法反转的时候需要注意的是：cur.next = run.next; run.next = cur; 核心代码
• 因为是反转部分代码，所以需要注意的是，记录下来第一个需要反转的位置，因为到时候它会变成第二部分的最后一个位置。

问题3

把一个长度为n的链表，按照长度为m的规则反转，注意的是n>=m>0

原理

• 首先，需要明确的是如何按照规则m反转，可以联想到使用stack来处理这个问题，stack是天然的先进后出的结构。
• 其次，在实现的时候每次获取m个元素存入栈中，然后依次把栈里的元素出栈，加入到新的链表里。在做加入stack之前把首节点dump下来。
• 最后，把剩余的部分元素加入到新的链表里，剩余部分的首节点，就是之前dump的节点。

代码

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head==null||k<=0){
            return head;
        }
        ListNode newHead = new ListNode(-1);
        ListNode run = newHead;
        ListNode dump = null;
        int count = k;
        Stack<ListNode> stack = new Stack<>();
        while(true){
            dump = head;
            while(head!=null&&count>0){
                stack.add(head);
                head = head.next;
                count--;
            }

            if(count>0){
                break;
            }

            while(!stack.isEmpty()){
                ListNode cur = stack.pop();
                run.next = cur;
                run = run.next;
            }
            count = k;
        }
        run.next = dump;
        return newHead.next;
    }
    
}

注意事项

• m这个数需要记录下来，每次进出stack之后需要恢复m
• 每次在开始加入stack之前，需要dump下head节点，目的是剩余的节点追加到新的链表里，需要一个记录头结点
• 设计的是永真循环，退出的条件是count>0,说明链表遍历完了，但是剩余元素不满足m个。