AlgoPressAppearance
24-反转链表
题目描述
https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
限制：
0 <= 节点个数 <= 5000
注意：本题与主站 206 题相同：https://leetcode.cn/problems/reverse-linked-list/
思路1：递归法
先传入null作为最后一个节点，header作为头指针 递归一定要注意把 前置节点 preNeode 传入进去用来作为 当前节点的 next
实现代码
csharp
public class Solution{
private ListNode ReverseListInternal(ListNode preNode, ListNode node){
if(node == null){
return preNode;
}
else{
ListNode tempNode = new ListNode(node.val, preNode);
return ReverseListInternal(tempNode, node.next);
}
}
public ListNode ReverseList(ListNode head) {
ListNode result = ReverseListInternal(null, head);
return result;
}
}
思路1：递归法2
思考递推公式，注意递归的时候，只考虑本层和下一层的关系 如 链表 1 -> 2 -> 3 -> 4 -> 5 我们要反转，可以把问题考虑为，我有首节点 head 指向 1， 然后有剩余节点 [2->3->4->5] 我们假设剩余节点已经翻转完 变成 1 -> [5->4->3->2] 注意翻转完之后， head.next 仍然是指向 2 的。 我们将 head.next.next 指向 1 ，即 head.next.next = head，注意此时要将 head.next 设置为 null 否则就会循环引用了
实现代码
csharp
public class Solution{
public ListNode ReverseList(ListNode head){
if(head == null || head.next == null){
return null;
}
ListNode node = ReverseList(head.next);
head.next.next = head;
head.next = null;
return node;
}
}
思路2：迭代法 使用Stack
实现代码
csharp
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode ReverseList(ListNode head) {
//迭代 (使用Stack)
Stack<int> stack = new Stack<int>();
ListNode tempNode = head;
while(tempNode != null){
stack.Push(tempNode.val);
tempNode = tempNode.next;
}
ListNode result=null;
if(stack.Count > 0){
result = new ListNode(stack.Pop(), null);
ListNode currentNode = result;
//process following
while(stack.Count > 0){
tempNode = new ListNode(stack.Pop(), null);
currentNode.next = tempNode;
currentNode = currentNode.next;
}
}
return result;
}
}
思路3 ： 迭代法，不使用 Stack
csharp
public class Solution{
public ListNode ReverseList(ListNode head){
ListNode prev = null;
ListNode cur = head;
while(cur != null){
ListNode temp = cur;
cur = cur.next;
temp.next = prev;
prev = temp;
}
return prev;
}
}