1.反转链表
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
示例一:
示例二:
示例三:
进阶:你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?
1.双指针实现
分析题目可知,我们可以采用双指针来对链表进行反转。
我建议大家可以现在草稿纸上写下指针变化的过程,再开始编写程序,尤其是涉及链表的问题!
具体的步骤如下所示:
定义两个指针: pre和 cur;pre在前 cur在后。
每次均用next指针保存cur.next,然后让 cur.next指向 pre,以实现一次局部反转;
局部反转完成之后,pre和 cur同时往后移动一个位置
循环上述过程,直至 pre到达链表尾部结束!
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
//双指针实现
ListNode pre=null;
ListNode cur=head;
while(cur!=null){
//将cur的下一节点存储下来
ListNode next=cur.next;
cur.next=pre;
pre=cur;
cur=next;
}
return pre;
}
}
2.GIF动图展示
按照上述的操作步骤,在结合GIF动图演示,一定可以做到深刻的理解该算法的实现过程以及原理!
3.时间复杂度分析
由于本次算法的实现仍然是遍历一次链表,直到cur指向null结束,因此算法的时间复杂度为 O ( n ) O(n) O(n),空间复杂度为 O ( 1 ) O(1) O(1)。该算法在LeetCode中的执行情况如下所示:
2.链表中的中间节点
给定一个头结点为 head 的非空单链表,返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。
示例一:
示例二:
1.快慢指针
分析此问题,我们可以采用双指针方法解决该问题。
分别定义一个fast快指针,一次移动两位,定义一个slow慢指针,一次移动一位,那么当fast遍历到链表的末尾时,slow位置所指的节点就是中间节点!
具体代码实现如下所示:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow=head;
ListNode fast=head;
while(fast!=null && fast.next!=null){
slow=slow.next;//慢指针移动一位
fast=fast.next.next;
}
return slow;
}
}
2.GIF动图演示
下面的GIF动图以链表{1,2,3,4,5,6,7,8}为例,采用快慢指针对其进行遍历,
3.时间复杂度分析
这里同样是对链表的一次遍历,时间复杂度为 O ( n ) O(n) O(n),由于只需要在常数空间存储两个指针即可,因此空间复杂度为 O ( 1 ) O(1) O(1);该算法在LeetCode中的执行情况如下所示: