反转链表-从入门到精通

反转链表是一道比较基础的问题，如果没有做过的话，第一次要在面试场上写出来还是有点困难的。面试官一般使用链表问题来评价面试者的编码能力。

1. 反转单链表

题意已经很明显了，就是给你一个单链表的头指针$head$，完成链表的反转，返回链表的新头部。对于这个问题，记住下面的算法：

public class ReverseLinkedList {
    
    public static ListNode reverse(ListNode head) {
        ListNode pre = null, cur = head, next;
        while(cur != null) {
            next = cur.next;// next先抓住cur的下一个，为的是调整完当前的节点，cur可以跳到下一个位置继续调整
            cur.next = pre;// 开始调整，把当前节点的next指针设置为pre（pre始终代表cur前驱节点）
            pre = cur;// pre指针前进
            cur = next;// cur指针前进
        }
        return pre;
    }
    
    private static class ListNode {
        int val;
        Node next;
    }
}

测评链接：https://leetcode.cn/problems/reverse-linked-list/

2. 反转双向链表

思路和上面的是一样的，只需要在反转的时候调整一下$pre$指针即可。

public class ReverseDoubleLinkedList {
    
    public static ListNode reverse(DoubleListNode head) {
        DoubleListNode pre0 = null, cur = head, next;
        while(cur != null) {
            next = cur.next;
            cur.next = pre0;
            cur.pre = next;
            pre0 = cur;
            cur = next;
        }
        return pre;
    }
    
    private static class DoubleListNode {
        int val;
        Node next, pre;
    }
}

3. 反转链表的一部分

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。例如：head = [1,2,3,4,5], left = 2, right = 4，返回[1,4,3,2,5]

题目链接：https://leetcode.cn/problems/reverse-linked-list-ii/

完成这个问题需要三步：

1. 找到那个需要反转的那一段链表；
2. 断开需要反转的那部分，把它进行反转；
3. 把反转后的链表重新放回原来的链表中去。

代码如下：

public class ReverseLinkedList2 {
    
    public static ListNode reverse(ListNode head, int left, int right) {
        if(head == null || left == right) return head;
        ListNode dummy = new ListNode(-1), pre, start, next, t;
        dummy.next = head;// 因为可能存在更换头部的问题，因此用这个节点统一处理
        pre = dummy;
        
        // 找到三个关键节点
        int i = 0;
        for(; i != left - 1; pre = pre.next, ++i);
        start = pre.next;
        t = pre;
        for(; i != right; t = t.next, ++i);
        next = t.next;
        // 找到三个关键节点
        
        // 断开链表
        t.next = null;
        
        // 反转 重连链表
        pre.next = reverse(start);
        start.next = next;
        // 反转 重连链表
        
        return dummy.next;
    }
    
    public static ListNode reverse(ListNode head) {
        ListNode pre = null, cur = head, next;
        while(cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
    
    private static class ListNode {
        int val;
        Node next;
        ListNode(int v) {
            val = v;
        }
    }
}

4. K 个一组翻转链表

题目来自于leetcode，原题。

如果会做上面那个题，那么这个题目也就不难了。只要把握住找到关键节点，断开，反转，重连这几个步骤即可。如下图所示：

代码如下：

public class ReverseLinkedListKGroup {
    
    public static ListNode reverse(ListNode head, int k) {
        if(head == null || k == 1) return head;
        ListNode dummy = new ListNode(-1), pre = dummy, start, next, t;
        dummy.next = head;
        int i;
        while(true) {
            // 找到pre start next 三个节点
            start = pre.next;
            i = 1;
            t = start;
            for(; i != k && t != null; t = t.next, ++i);
            if(t != null) {
                next = t.next;
                t.next = null;
            } else break; // 如果t==null说明不够k个元素了，直接退出
            // 找到pre start next 三个节点
            
            // 反转 重连
            pre.next = reverse(start);
            start.next = next;
            
            // 更新pre 继续下一组
            pre = start;
        }
        return dummy.next;
    }
    
    public static ListNode reverse(ListNode head) {
        ListNode pre = null, cur = head, next;
        while(cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
    
    private static class ListNode {
        int val;
        Node next;
        ListNode(int v) {
            val = v;
        }
    }
}