这是整理的第18个题。
学会分析一个就足够了
累计记录
类似题目
链表为了 完成o(1)插入，需要定义2个节点
head，tail 目前这是标准2个方式。
这个是不会发生变化的。--需要一个头节点
vs
--------------------开始------------------------
leetcode-206 反转一个单链表。
reverse-linked-list
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
方法一 ：迭代（链表前插）
- 分析
也许你做过很多遍了，
但是真正发现里面变化规律。
发现以前认识不到地方
这是一个基本题目，考察绘制过程图
观察规律
描述：
- 假设链表第一个节点 就是最后最后一个节点 end（最后一个节点如何表示为head呢），end始终保持不变
- 最后一个节点 end 需要指向 end.next.next ,因为end.next 插入head后面
- 在遍历过程中，变化的start节点
用头节点来固定
- code
class Solution {
public:
/**
Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL
Output:5->4->3->2->1->NULL
演示 第一节点 如何变成最后一个节点的
end cur
| |
| |
start->1->2->3->4->5->NULL (初始化)
(3) (2) (1) 发送了3个变化
start: 2 ->1->3->4->5->NULL (反转1次后仍然是完整链表)
| |
| |
end cur
（3）（2） （1）
start: 3 ->2 ->1->4->5->NULL (反转2次后仍然是完整链表)
| |
| |
end cur
理解偏差
1 结合反转2考虑一下，这是一个链表，不是去构造另外一反转前的链表和反转后的链表，主要上学记住了构造新的链表。理解偏差1
2 理解偏差2 虽然知道反转第一个节点，变成最后一个阶段，但是根本理解有什么用
开始之后1--2
最后一个1--NUll
循环做好准备
3 有没有造成死循环 1 --NULL 产生方式。理解有点模糊 ，还是判断cur是否为null
4.理解偏差3
默认第一个节点是返回第一节点也是最后一个节点，这里无法区分 1->next 含义是开始还end的操作
1->next 是怎么变化的
复杂度分析
时间复杂度：O(n)
空间复杂度：O(1)
**/
ListNode* reverseList(ListNode* head)
{
ListNode start(-1);
start.next=head;//保证 start 一定存在，才可以执行start.next
ListNode* end=head;//默认第一个节点是翻转链表最后一个节点
ListNode* cur=NULL;
while(end &&end->next)
{
cur=end->next;
end->next=cur->next;//(1) 1--4
cur->next=start.next;//(2) 3-2-1
start.next=cur;//(3) // 3-2-1-5
}
return start.next;
}
};
- 复杂度分析
时间复杂度：O(n)
空间复杂度：O(1)
方法二：递归（链表后插）
递归版本稍微复杂一些，其关键在于反向工作。假设列表的其余部分已经被反转，现在我该如何反转它前面的部分？
逻辑
- code
/**
head head.next
input： 1-->2-->3-->4-->5-nill
(head)
第一次：1-->2-->3 ---4-NUll
5-->4--NUll
3和5都指向节点4
第二次：1-->2-->3
5-->4-3-NULL
last次：5-->4-3-2->1NULL
**/
func reverseList(head *ListNode) *ListNode {
if head ==nil ||head.Next==nil {
return head //最后一个节点返回，head==nil为防止输入的为nill
}
first:=reverseList(head.Next)
head.Next.Next=head //第k个节点放到第k+1后面
head.Next=nil
return first
}
- 复杂度分析
时间复杂度：O(n)
空间复杂度：O(n)
由于使用递归，将会使用隐式栈空间。
网友评论