2020-11-13 | 代码如诗 | UNLOCK

反转链表-力扣206 迭代

反转链表听起来蛮难的,但是也就是一次迭代改变链表中指针的指向,将其反向指回去。这种方法比复制一个链表出来效率要高。当然,作为单向链表来说,去复制链表也不是什么简单的好办法。

题干

[力扣-反转链表]

反转一个单链表。
示例:

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

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?

迭代

思路

说实话迭代是什么也不是很理解,廖雪峰有一篇文章介绍了迭代:[廖雪峰的官网] 大致上可以理解为遍历吧。大致过程就是不断的改变指针指向,将本节点指向下一个节点的指针指向上一个节点,因此需要临时的结构体指针来保存节点(毕竟是单向链表,不能回去)。为了方便理解,粗略的画了一下图,在实际应用中关于链表的问题画图确实比较好理解一些。(u1s1,surface的笔是真的爽,买电脑不能只看性能啊,另外字太丑了…)

图一
在开始的时候,定义临时节点nextNode,然后更改head->next指向NULL,然后定义临时节点lastNode用于保存上一节点,将head指向nextNode

图二
循环,修改nextNodelastNodehead等指针的指向,不断的将节点->next反转,并向前移动head

图三
head->next == NULL的时候即为最后一个节点,此时结束循环并修改最后一个节点的指向,然后返回链表。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* 单向链表的结构体定义
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/


struct ListNode *reverseList(struct ListNode *head)
{
struct ListNode *lastNode = head;
struct ListNode *temp = head;

if (head != NULL && head->next != NULL)
{
for (int isFirst = 1; head->next != NULL; temp = head)
{
head = head->next;
if (isFirst == 1)
{
temp->next = NULL;
isFirst = 0;
}
else
{
temp->next = lastNode;
}
lastNode = temp;
}
head->next = lastNode;
}
return head;
}

这次只使用了C语言,因为C#反转链表应该不难,list.Reverse();(逃)

结果

仅有一次循环,使用迭代的方法还是蛮快的,完成了力扣的任务。但是递归我实在不会,甚至不能很好的区分它们。所以暂时就没有写递归方法。
力扣

最后

这道题的话还是比较简单的,毕竟画起图来感觉不难,但是实际写起来还是有一定挑战性的。通过这道题顺手复习了忘干净的链表,也是非常好的。链表的题先画图理解一下有很大帮助,尤其是自己用笔手动遍历一下,利于理解过程。

评论加载中