206、反转链表
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
题解
1、头插法
利用辅助指针和伪头节点，实现头插法算法，完成链表的反转。
注意：
- 刚开始辅助指针的赋值
- 最后的尾节点的赋值。
- 重新设置头节点。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
// 头插法
if (head == null || head.next == null) {
return head;
}
// 伪头结点
ListNode dummy = new ListNode(-1);
// 辅助引用变量，相当于指针
ListNode p,q;
// 初始化值
dummy.next = head;
p = head.next;
head.next = null;// 作为新的尾部结点
while (p != null) {
q = p.next;// 获取下一个待反转结点
p.next = dummy.next;// 反转当前结点的 next 属性
dummy.next = p;// 将当前将结点反转成头节点
p = q;// 更新当前结点
}
// 确定新的头节点
head = dummy.next;
return head;
}
}
2、递归实现链表反转
理解递归的作用：
- 利用了递归栈，最后一次调用，第一个返回。
- 利用了引用复制，即：传进去的节点引用被复制了，存在于递归调用的作用域内。
其实递归可以看成是尾插法生成链表。
描述：
- 递归边界条件，当前节点为空或者没有后继节点
- 递归遍历到尾节点
- 递归回溯
- 拿到dummy节点
- 将头节点的索引到下一个节点的next指针上
- 将头节点的nexts索引重置为 null 避免出现环
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
// 递归结束
if (head == null || head.next == null) {
return head;
}
// 递归获取新的头节点，head.next 被复制为新的head
ListNode dummy = reverseList(head.next);
// 将head节点反转成新的尾节点
// from head -> next -> next1 -> null to head -> next -> next1 -> head
head.next.next = head;
// 尾节点的next为空
// from next -> next -> head to head -> next -> null | next1 -> head to avoid circle
head.next = null;
// 返回新的头节点
return dummy;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
