大厂高频算法面试题：《链表反转系列》，面试官想考察的目的：手稳不稳，coding能力，指针指向问题，链表反转几乎是高频中高频，您将学到通过有限变量即可实现链表反转，快来一起学习吧！

一、反转单向链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

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

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

leetcode

1、分析

给定一个单链表的头head，完成链表的逆序调整。

方法一：有限变量搞定，定义两个变量，pre指针，next指针，pre指针指向当前节点的上一个节点，next指针指向当前节点的下一个节点。最优解，时间复杂度O(N)，额外空间复杂度O(1)

方法二：递归

2、实现

1、方法一

public static class ListNode {
    int val;
    ListNode next;
}

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

2、方法二

public static class ListNode {
    int val;
    ListNode next;
}   

public static ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode newList = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newList;
}

二、反转双向链表

给定一个双链表的头head，完成链表的逆序调整

1、分析

提前记录下一个节点next，当前节点的next指向pre，当前节点的last指向next，pre的next指向当前节点，当前节点跳下一个

2、实现

// 双链表定义
public static class DoubleNode {
    public int value;
    public DoubleNode last;
    public DoubleNode next;

    public DoubleNode(int data) {
        value = data;
    }
}

// 双链表反转（两个指针搞定）
public static DoubleNode reverseDoubleList(DoubleNode head) {
    DoubleNode pre = null;
    DoubleNode next = null;
    while (head != null) {
        next = head.next;
        head.next = pre;
        head.last = next;
        pre = head;
        head = next;
    }
    return pre;
}

三、反转部分单向链表

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]

进阶： 你可以使用一趟扫描完成反转吗？

leetcode

1、分析

可能存在换头的情况，所以函数应该返回调整后的新节点。

方法一：遍历一遍链表，先找到left和right节点，即反转链表的开始部分和结束部分。

1. 先判断是否满足 1≤left≤right≤N，如果不满足，则直接返回原来的头节点。
2. 找到第left-1个节点fPre和第right+1个节点tPos，fPre就是要反转部分的前一个节点，tPos是反转部分的后一个节点。把反转部分先反转，然后正确的连接fPre和tPos
3. 如果fPre为null，说明反转部分是包含头节点的，则返回新的头节点，如果fPre不为null，则返回旧的头节点。

方法二：利用头插法进行反转链表，待反转的节点每次都往头部插入。

2、实现

1、方法一

public static class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

// 找到反转链表的开始节点和结束节点，正常反转
public ListNode reverseBetween(ListNode head, int from, int to) {
    int len = 0;
    ListNode node1 = head;
    ListNode fPre = null; // from节点的前一个节点
    ListNode tPos = null; // to节点的下一个节点
    while (node1 != null) { // 找到反转链表开始节点的前一个节点和结束节点的下一个节点
        len++;
        fPre = len == from - 1 ? node1 : fPre;
        tPos = len == to + 1 ? node1 : tPos;
        node1 = node1.next;
    }
    if (from > to || from < 1 || to > len) {
        return head;
    }
    node1 = fPre == null ? head : fPre.next;
    ListNode node2 = node1.next;
    node1.next = tPos;
    ListNode next = null;
    while (node2 != tPos) { // 反转from到to上的节点
        next = node2.next;
        node2.next = node1;
        node1 = node2;
        node2 = next;
    }
    if (fPre != null) {
        fPre.next = node1;
        return head;
    }
    return node1;
}

2、方法二

public static class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

public static ListNode reverseBetween(ListNode head, int left, int right) {
    if (head == null || left == right) {
        return head;
    }
    ListNode newHead = new ListNode(0);
    newHead.next = head;
    ListNode pre = newHead;
    for (int i = 0; i < left - 1; i++) {
        pre = pre.next;
    }
    ListNode cur = pre.next;
    ListNode next = null;
    for (int i = 0; i < right - left; i++) {
        next = cur.next;
        cur.next = next.next;
        next.next = pre.next;
        pre.next = next;
    }
    return newHead.next;
}

四、总结

链表相关的问题几乎都是coding问题，手稳不稳！指针指向问题！

单链表：值，一条next指针

双链表：值，一条pre指针，一条next指针

玩出无尽的花样！