206. 反转链表
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
Categories:
题意:
翻转给定的链表
示例:
输入:head = [1,2,3,4,5] 输出:[5,4,3,2,1]
难度:
简单
分析:
链表翻转有两种方法
- 迭代
- 递归
这里我们用迭代法
从图中可以看出, 对链表的翻转可以理解为箭头方向变化
这样我们可以讲链表转为两两一组的节点对, 从头开始迭代
对于节点对, 我们分为首节点和次节点, 在单向链表, 次节点指向其他节点, 一旦断开次节点的引用, 其他节点会丢失
所以需要提前存储其他节点
改变引用关系大致流程如下:
- 获得首节点
- 临时存储其他节点
- 次节点指向首节点
- 迭代, 次节点为下一代的首节点, 临时存储节点为次节点
class Solution {
public ListNode reverseList(ListNode head) {
//迭代法
ListNode current = head;
ListNode previous = null;
while(current != null){
ListNode temp = current.next;
current.next = previous;
previous = current;
current = temp;
}
return previous;
}
}