反转链表
题目：描述
给定一个单链表的头结点head，长度为n，反转该链表后，返回新链表的表头。
反转链表.png
以上转换过程如下图所示：
示例1
输入：
{1,2,3}
返回值：
{3,2,1}
示例2
输入：
{}
返回值：
{}
复制
说明：
空链表则输出空
1.迭代法
因为单链表只能由当前节点查找到后一个节点，因此使用迭代法时，需要保存当前节点的后一个节点。
- curr 指向链表的当前节点，next 保存curr节点的下一个节点（因为是单链表，不保存的话，改变方向之后就找不到旧节点的下个节点了），prev刚开始值为空，保存当前节点的前一个节点。
反转列表-迭代法.drawio.png
- 假如单链表为[1,2,3,4,5],curr指向第一个节点1，核心代码如下：
next = curr.next //先保存next节点，防止节点断后，找不到下一个节点
curr.next = prev
prev = curr, curr = next
Java代码实现：
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
// 如何调整链表指针，达到链表反转的目的。
ListNode prev = null; // prev : 指向反转好节点的最后一个节点
ListNode curr = head; //指向反转链表的第一个节点
while(curr != null){
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
Python代码如下：
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
prev = None
curr = head
while curr is not None:
next = curr.next
curr.next = prev
prev, curr = curr, next
return prev # 注意：此时prev节点指向最后一个节点
2.使用“栈”
由于栈的特点：先入后出，假如要反转的链表为[1, 2, 3, 4, 5]，我们把每个节点压入到栈中，然后再取出就可以得到反转后的节点[5, 4, 3, 2, 1]。具体步骤如下：
栈-反转链表.drawio.png
- 遍历链表，把每个节点依次压入栈中。
- 再遍历取出，就实现了链表的反转
代码如下：
java实现：
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
import java.util.Stack;
public class Solution {
public ListNode ReverseList(ListNode head) {
Stack<ListNode> stack = new Stack<>(); // 栈
// 1.把链表中的节点入栈
while(head != null){
stack.push(head);
head = head.next;
}
// 2.判断栈为空，则返回null
if(stack.isEmpty())
return null;
// 3.从栈中取出元素，然后组成链表，则为反转后的链表
ListNode dummy = stack.pop();
ListNode temp = dummy;
while(!stack.isEmpty()){
temp.next = stack.pop();
temp = temp.next;
}
// 4.最后一个节点的next要置为空，否则会构成环
temp.next = null;
return dummy;
}
}
Python代码：
def ReverseList(self , head: ListNode) -> ListNode:
# write code here
stack = [] #使用列表即可实现栈
while head is not None:
stack.append(head)
head = head.next
if len(stack) == 0:
return None
dummy = stack.pop() # 哑结点
temp = dummy
while len(stack) != 0:
temp.next = stack.pop()
temp = temp.next
# 最后一个节点是反转前的头结点，一定要让他的next等于空，否则会构成环
temp.next = None
return dummy
3.新建链表法
如图所示：遍历单链表中的每一个节点，一个一个进行链接，如下图所示：
新建链表.drawio.png
Python代码如下：
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
# 双链表法：
dummy = None # 定义空节点
while head is not None:
next = head.next # 因为是单链表，先保存下一个节点
head.next = dummy # 第一个节点连接到 dummy
dummy, head = head, next # dummy 指向最新的节点，head指向下一个节点，进行遍历
return dummy # 结束后 dummy 将指向新节点的头结点
java代码：
class Solution {
public ListNode reverseList(ListNode head) {
// 1.定义哑结点 dummy
ListNode dummy = null;
while(head != null){
// 2.先保存下一个节点
ListNode next = head.next;
// 3.原链表中的第一个节点指向dummy
head.next = dummy;
// 4.dummy 指向 head，head指向下一个节点
dummy = head;
head = next;
}
return dummy;
}
}
4.递归法
反转链表.drawio.png
如图所示
思路：
- 开始head指向第一个节点
- 递归到倒数第二个节点
- 然后改变节点的方向
- 找到递归的出口，反方向回来
def reverse_list(self, head):
if head is None or head.next is None: # 递归结束条件
return head
else:
ans = self.reverse_list(head.next) # 递归下一个结点 到 倒数第二个结点
head.next.next = head # 最后一个结点指向倒数第二个结点
head.next = None # 最后一结点的指针域赋值为空
return ans
