方法一:迭代
假设链表为 1→2→3→∅,我们想要把它改成 ∅←1←2←3。
在遍历链表时,将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点,因此必须事先存储其前一个节点。在更改引用之前,还需要存储后一个节点。最后返回新的头引用。
class Solution {
public ListNode reverseList(ListNode head) {
//申请节点,pre和 cur,pre指向null
ListNode pre = null;
ListNode cur = head;
ListNode tmp = null;
while(cur!=null) {
//记录当前节点的下一个节点
tmp = cur.next;
//然后将当前节点指向pre
cur.next = pre;
//pre和cur节点都前进一位
pre = cur;
cur = tmp;
}
return pre;
}
}
复杂度分析
方法二:递归
终止条件是当前节点或者下一个节点==null
以1->2->3->4->5
这个链表为例,整个递归调用的执行过程,对应到代码层面(用java做示范)是怎么执行的,以及递归的调用栈都列出来了
class Solution {
public ListNode reverseList(ListNode head) {
//递归终止条件是当前为空,或者下一个节点为空
if(head==null || head.next==null) {
return head;
}
//这里的cur就是最后一个节点
ListNode cur = reverseList(head.next);
//这里请配合动画演示理解
//如果链表是 1->2->3->4->5,那么此时的cur就是5
//而head是4,head的下一个是5,下下一个是空
//所以head.next.next 就是5->4
head.next.next = head;
//防止链表循环,需要将head.next设置为空
head.next = null;
//每层递归函数都返回cur,也就是最后一个节点
return cur;
}
}
head指向1,head.next指向2传入下一个reverseList()方法
head指向2,head.next指向3传入下一个reverseList()方法
head指向3,head.next指向4传入下一个reverseList()方法
head指向4,head.next指向5传入下一个reverseList()方法
head指向5,head.next指向null,此时的reverseList()返回5
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)