前言

反转链表是程序员必备的基本素养,经常在面试、笔试的过程中泛起。一直以为反转链表实现代码不是很好明白,决议搬leetcode那道经典反转链表题出来,用十多张图去剖析它,希望加深人人对链表反转的明白,谢谢阅读。

leetcode的反转链表原题&谜底

问题形貌: 反转一个单链表。

输入:

1
->
2
->
3
->
4
->
5
->
NULL
输出:

5
->
4
->
3
->
2
->
1
->
NULL

剖析:

假设存在链表 1 → 2 → 3 → Ø,我们想要把它改成 Ø ← 1 ← 2 ← 3。

在遍历列表时,将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点,因此必须事先存储其前一个元素。在更改引用之前,还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用!

代码实现:

public

ListNode
 reverseList
(
ListNode
 head
)

{

ListNode
 prev 
=

null
;

ListNode
 curr 
=
 head
;

while

(
curr 
!=

null
)

{

ListNode
 nextTemp 
=
 curr
.
next
;
        curr
.
next

=
 prev
;
        prev 
=
 curr
;
        curr 
=
 nextTemp
;

}

return
 prev
;
}

图解链表反转代码的实现

接下来,我们图解以上代码实现,先对以上实现代码加上行号,如下:

public

ListNode
 reverseList
(
ListNode
 head
)

{

//1

ListNode
 prev 
=

null
;

// 2

ListNode
 curr 
=
 head
;

// 3

while

(
curr 
!=

null
)

{

//4

ListNode
 nextTemp 
=
 curr
.
next
;

//5
        curr
.
next

=
 prev
;

// 6
        prev 
=
 curr
;

//7
        curr 
=
 nextTemp
;

//8

}

return
 prev
;

//9
}

第一行代码图解

public

ListNode
 reverseList
(
ListNode
 head
)

{

//1

我们顺着问题形貌意思,假设链表就有1、2、3个元素吧,后面还跟着一个null,又由于输入是ListNode head,以是这个即将要反转的链表如下:

第二行代码图解

ListNode
 prev 
=

null
;

// 2


将null赋值给prev,即prev指向null,可得图如下:

第三行代码图解

ListNode
 curr 
=
 head
;

将链表head赋值给curr,即curr指向head链表,可得图如下:

循环部门代码图解

while

(
curr 
!=

null
)

{

//4

ListNode
 nextTemp 
=
 curr
.
next
;

//5
        curr
.
next

=
 prev
;

// 6
        prev 
=
 curr
;

//7
        curr 
=
 nextTemp
;

//8

}

循环部门是链表反转的焦点部门,我们先走一遍循环,图解剖析一波。

由于curr指向了head,head不为null,以是进入循环。先来看第5行:

ListNode
 nextTemp 
=
 curr
.
next
;

//5

把curr.next 赋值给nextTemp变量,即nextTemp 指向curr的下一节点(即节点2),可得图如下:

再执行到第6行:

curr
.
next

=
 prev
;

// 6

把prev赋值给curr.next,由于prev初始化化指向null,即curr(节点1)指向了null,链表图解成这样了:

,

以太坊高度数据

www.326681.com采用以太坊区块链高度哈希值作为统计数据,联博以太坊统计数据开源、公平、无任何作弊可能性。联博统计免费提供API接口,支持多语言接入。

,

然后我们看执行到第7行

 prev 
=
 curr
;

//7

把curr赋值给prev,prev指向curr,图解如下:

接着,我们执行到第8行:

curr 
=
 nextTemp
;

//8

把nextTemp赋值给curr,即curr指向nextTemp,图解如下:

至此,第一遍循环执行竣事啦,回到循环条件,curr依旧不为null,我们继续图解完它。

5-8行代码又执行一遍,依次可得图:

ListNode
 nextTemp 
=
 curr
.
next
;

//5
        curr
.
next

=
 prev
;

// 6
        prev 
=
 curr
;

//7
        curr 
=
 nextTemp
;

//8

执行完 ListNodenextTemp=curr.next;后:

执行完 curr.next=prev;后:

执行完 prev=curr;后:

执行完 curr=nextTemp;后:

来到这里,发现curr照样不为null,再回到while循环,再执行一遍:


ListNode
 nextTemp 
=
 curr
.
next
;

//5
        curr
.
next

=
 prev
;

// 6
        prev 
=
 curr
;

//7
        curr 
=
 nextTemp
;

//8

依次可得图:




来到这里,我们发现curr已经为null了,可以跳出循环了。这时候prev指向的就是链表的反转呀,以是第9行执行完,反转链表功效实现:


return
 prev
;

//9

参考与谢谢

  • LeetCode 官网

小我私家民众号

  • 若是你是个爱学习的好孩子,可以关注我民众号,一起学习讨论。
  • 若是你以为本文有哪些不正确的地方,可以谈论,也可以关注我民众号,私聊我,人人一起学习提高哈。