题目描述: 反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
记录now.next,反转now.next, 后移prev,后移now;
now
的后继,先用next
将now
原后继记录下来;
想要改变now
,先用prev
记录下来;
执行草图:
代码:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode now = head;
while (now != null) {
ListNode next = now.next; //next 指向now.next
now.next = prev; //now.next 指向prev
prev = now;
now = next;
}
return prev;
}
}
解法思路如下:
now
反转前的下一个节点now.next
纪录下来,即ListNode next = now.next;
记录下来的原因是最后第四行要用,
让本轮的now结点能往后移动;now.next
置为反转前的上一节点prev
,即now.next = prev;
prev = now;
next
变为当前节点now
;即now = next;
now != null
即next不为空,表示链表还有节点未处理,
最后now == null
,即链表已尽,
此时,next = now = 表尾往后一个“节点”(null)
,
prev
指向反转前最后一个
节点,
也即反转后第一个
节点;
跳出while
循环,
所以最后return prev;
运行效果:
思路如下:
0.利用递归首先找到单链表的最后一个节点;
最后一个节点
存储在re
里面,
re
在找到最后一个节点时被赋值且其永远为最后一个节点的值,保持不变;
从找到最后一个节点开始,
从最后往前的方向,每一层递归反转一对节点 / 一个指向;
head == null ||
)或者是否是链表的最后一个节点
(递归终止条件);next
;next = head.next;
head.next = null;
next
丢进递归;
找到最后一个节点的时候会return
回来;next.next = head;
6.返回核心同样是四行代码,(可以结合运行草图理解) 前两行不断剪除原来的指向 ListNode next = head.next; //next 指向head.next head.next = null; //剪除原来的指向 ListNode re = reverseList(next); //递归找到末节点,记录下来付给re next.next = head; //反转指向
代码:
/**
* 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 next = head.next;
head.next = null;
ListNode re = reverseList(next);
next.next = head;
return re;
}
}
运行草图:
Leetcode提交结果:
注意:
要if判断中要加上head == null ||
,防止输出空链表的情况;
否则会报空指针的错:java.lang.NullPointerException
1.哈希表 while(head != null)判断是否为表尾; nodes.add(head);如果新节点没有包含,吃进去,一直吃; 终焉两种情况, 2.1. 无环,直到head == null还没重复,false 2.2. 有环,if(nodes.contains(head))直到加到重复的,true
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
Set<ListNode> nodes = new HashSet<>();
while(head != null){
if(nodes.contains(head))
return true;
else
nodes.add(head);
head = head.next;
}
return false;
}
}
复杂度分析
时间复杂度:O(n)O(n),对于含有 nn 个元素的链表,我们访问每个元素最多一次。添加一个结点到哈希表中只需要花费 O(1)O(1) 的时间。
空间复杂度:O(n)O(n),空间取决于添加到哈希表中的元素数目,最多可以添加 nn 个元素。
2.双指针:
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
终焉两种情况: 3.1. 有环,迟早追上 slow == fast 跳出循环,true;
3.2. 无环,快针迟早到链尾,flase if (fast == null || fast.next == null) { return false; }
复杂度分析
时间复杂度:O(n)O(n),让我们将 nn 设为链表中结点的总数。为了分析时间复杂度,我们分别考虑下面两种情况。
链表中不存在环: 快指针将会首先到达尾部,其时间取决于列表的长度,也就是 O(n)O(n)。
链表中存在环: 我们将慢指针的移动过程划分为两个阶段:非环部分与环形部分:
慢指针在走完非环部分阶段后将进入环形部分:此时,快指针已经进入环中 \text{迭代次数} = \text{非环部分长度} = N迭代次数=非环部分长度=N
两个指针都在环形区域中:考虑两个在环形赛道上的运动员 - 快跑者每次移动两步而慢跑者每次只移动一步。其速度的差值为 1,因此需要经过 \dfrac{\text{二者之间距离}}{\text{速度差值}} 速度差值 二者之间距离 次循环后,快跑者可以追上慢跑者。这个距离几乎就是 "\text{环形部分长度 K}环形部分长度 K" 且速度差值为 1,我们得出这样的结论 \text{迭代次数} = \text{近似于}迭代次数=近似于 "\text{环形部分长度 K}环形部分长度 K".
因此,在最糟糕的情形下,时间复杂度为 O(N+K)O(N+K),也就是 O(n)O(n)。
空间复杂度:O(1)O(1),我们只使用了慢指针和快指针两个结点,所以空间复杂度为 O(1)O(1)。