终于学会反转链表了｜leetcode206、nc78（cpp、java实现）

前期提要：

链表反转是高频考点，在各大高频题排名网站长期占领前三，在牛客网稳居第一。

链表反转之所以很重要，是因为它在实际编程中应用广泛，可以解决很多与链表相关的问题。一些算法和数据结构需要借助链表来实现，比如LRU缓存淘汰算法、数据结构栈和队列等等。而链表的反转是其中一个最基本的操作，通过反转可以使得链表的遍历顺序与原来相反，这样就可以更方便实现一些算法和问题的解决。同时，链表反转也是一道经典的面试题，掌握链表反转的方法可以帮助程序员在面试中获得更好的表现。

题目来源：牛客nc78；力扣leetcode206

本题有两种方法，带头结点和不带头结点，由不带头结点又可以引申出第三种方法——递归。

方法一：虚拟节点法（头插法）

1. 首先，创建一个虚拟节点，并将其指向原链表的头节点，让我们称之为dummy节点。这样做的好处是，无论头节点是否为null，我们都可以在dummy节点上进行操作。
2. 接着，定义两个指针，一个指向当前节点（curNode），一个指向当前节点的前一个节点（prevNode）。
3. 然后，我们开始遍历整个链表。每次迭代中，我们将curNode的next指向prevNode，然后将prevNode和curNode都向后移动一个位置。
4. 继续循环直到curNode变为null，遍历完成。
5. 最后，让dummy节点指向prevNode，即完成了链表的反转。记得释放dummy节点哦～

【在代码中我们用ans来代表dummy（虚拟）节点】

C++中的虚拟节点（Virtual Node）通常指的是在链表或树等数据结构中，为了简化操作或者提升性能而添加的一个额外节点。虚拟节点并不存储实际的数据，它只是作为辅助节点存在。

在链表中，虚拟节点可以用来简化插入和删除操作。通常链表的头节点是特殊处理的，因为需要记录链表的起始位置。如果没有虚拟节点，插入和删除操作就需要单独处理头节点的情况。而有了虚拟节点，头节点和其他节点的处理方式就一致了，操作起来更加简洁。

在树中，虚拟节点可以用来处理边界情况。例如，在二叉搜索树中，如果要插入一个新节点，但树为空，那么可以将新节点作为虚拟节点插入，并将其作为根节点。这样可以避免在处理空树时需要特殊处理的情况。

总的来说，虚拟节点是一种在数据结构中添加一个额外节点来简化操作或处理边界情况的技术。它并不存储实际数据，只起到辅助作用。

cpp复制代码/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
         ListNode *ans=new ListNode(-1);
         ListNode *cur=head;
         while(cur!=nullptr){
             ListNode *next=cur->next;
             cur->next=ans->next;
             ans->next=cur;
             cur=next;
         }
         return ans->next;
    }
};
           

java复制代码/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode ans=new ListNode(-1);
        ListNode cur=head;
        while(cur!=null){
            ListNode next=cur.next;
            cur.next=ans.next;
            ans.next=cur;
            cur=next;
        }
        return ans.next;
    }
}
           

不过这种方法可能会被面试官禁止，因为不借助虚拟结点的方式更难，更能考察面试者的能力。

方法二：双指针迭代法

直接操作链表实现反转

1. 首先定义两个指针pre和cur，初始化时pre=head，cur=head.next；
2. 遍历链表，每次将cur指向的节点插入到pre之后，即cur.next=pre；
3. 操作完成后，将pre和cur往后移动一个节点，即pre=cur，cur=cur.next；
4. 重复步骤2和步骤3，直到cur为空，此时pre所指的节点为反转后的链表头，返回pre即可。

直接修改，要注意设两个指针

cpp复制代码/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *currNode=head,*preNode=nullptr;
        while(currNode!=nullptr){
            ListNode *next=currNode->next;
            currNode->next=preNode;
            preNode=currNode;
            currNode=next;           
        }
        return preNode;
    }
};
           

java复制代码/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode p1=null,p2=head;//p1为pre，p2为cur
        while(p2!=null){
            ListNode next=p2.next;
            p2.next=p1;
            p1=p2;
            p2=next;
        }
        return p1;
    }
}
           

我写的时候虽然用对了双指针，用对了判断条件，但是忽略了ListNode *next=currNode->next;这一步。

为什么ListNode *next=currNode->next;不可缺少？

因为在反转链表的过程中，我们需要保留当前节点的下一个节点的引用，以便后续的遍历。如果缺少了这一步，我们将无法继续遍历链表并对每个节点进行反转操作。

将上面这段代码在理解的基础上背下来，因为这个算法太重要

方法三：递归

1. 当链表为空或只有一个节点时，直接返回该链表；
2. 用递归反转除第一个节点之外的链表，返回新的头节点newHead；
3. 将第一个节点head连接到newHead之后，形成新的头节点；
4. 返回新的头节点。

java复制代码public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
    return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
           

cpp复制代码struct ListNode* reverseList(struct ListNode* head){
    if (head == NULL || head->next == NULL) {
        return head;
    }

    struct ListNode* newHead = reverseList(head->next);

    head->next->next = head;
    head->next = NULL;

    return newHead;
}
           

扩展题型

反转链表是一道经典的算法题，它需要我们将链表中的节点顺序完全颠倒过来。除了常见的反转链表外，还有一些类似的题型，比如：

1. 反转链表：将链表的节点顺序完全颠倒过来；（lLeetCode206）
2. 反转链表的一部分：将链表中指定区间的节点顺序完全颠倒过来；（LeetCode92）
3. 每k个节点反转链表：将链表中每k个节点的顺序进行反转；
4. K个一组反转链表：将链表按照每k个节点一组进行反转，不满k个节点不做处理；（LeetCode25）
5. 反转每对相邻节点：将链表中每对相邻节点的顺序进行反转。（LeetCode24）

作者：染落林间色

链接：https://juejin.cn/post/7260385528869322807