终于学会反转链表了｜leetcode206、nc78（cpp、java实现）
前期提要：
链表反转是高频考点，在各大高频题排名网站长期占领前三，在牛客网稳居第一。
链表反转之所以很重要，是因为它在实际编程中应用广泛，可以解决很多与链表相关的问题。一些算法和数据结构需要借助链表来实现，比如LRU缓存淘汰算法、数据结构栈和队列等等。而链表的反转是其中一个最基本的操作，通过反转可以使得链表的遍历顺序与原来相反，这样就可以更方便实现一些算法和问题的解决。同时，链表反转也是一道经典的面试题，掌握链表反转的方法可以帮助程序员在面试中获得更好的表现。🙂
题目来源：牛客nc78；力扣leetcode206
本题有两种方法，带头结点和不带头结点，由不带头结点又可以引申出第三种方法——递归。
方法一：虚拟节点法（头插法）
【在代码中我们用ans来代表dummy（虚拟）节点】
C++中的虚拟节点（Virtual Node）通常指的是在链表或树等数据结构中，为了简化操作或者提升性能而添加的一个额外节点。虚拟节点并不存储实际的数据，它只是作为辅助节点存在。
在链表中，虚拟节点可以用来简化插入和删除操作。通常链表的头节点是特殊处理的，因为需要记录链表的起始位置。如果没有虚拟节点，插入和删除操作就需要单独处理头节点的情况。而有了虚拟节点，头节点和其他节点的处理方式就一致了，操作起来更加简洁。
在树中，虚拟节点可以用来处理边界情况。例如，在二叉搜索树中，如果要插入一个新节点，但树为空，那么可以将新节点作为虚拟节点插入，并将其作为根节点。这样可以避免在处理空树时需要特殊处理的情况。
总的来说，虚拟节点是一种在数据结构中添加一个额外节点来简化操作或处理边界情况的技术。它并不存储实际数据，只起到辅助作用。
/**
* 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;
}
};
/**
* 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;
}
}
不过这种方法可能会被面试官禁止，因为不借助虚拟结点的方式更难，更能考察面试者的能力。
方法二：双指针迭代法
直接操作链表实现反转
直接修改，要注意设两个指针
/**
* 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;
}
};
/**
* 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;不可缺少？
因为在反转链表的过程中，我们需要保留当前节点的下一个节点的引用，以便后续的遍历。如果缺少了这一步，我们将无法继续遍历链表并对每个节点进行反转操作。
将上面这段代码在理解的基础上背下来，因为这个算法太重要
方法三：递归
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;
}
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;
}
扩展题型
反转链表是一道经典的算法题，它需要我们将链表中的节点顺序完全颠倒过来。除了常见的反转链表外，还有一些类似的题型，比如：
关于链表的相关题型还会持续更新，点个关注不迷路～欢迎私信我和我交流。
