六六力扣刷题双指针之反转链表

简介: 六六力扣刷题双指针之反转链表

前言

之前小六六一直觉得自己的算法比较菜,算是一个短板吧,以前刷题也还真是三天打鱼,两天晒网,刷几天,然后就慢慢的不坚持了,所以这次,借助平台的活动,打算慢慢的开始开刷,并且自己还会给刷的题总结下,谈谈自己的一些思考,和自己的思路等等,希望对小伙伴能有所帮助吧,也可以借此机会把自己短板补一补,希望自己能坚持下去呀

链表的合集

字符串

双指针

题目

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

image.png

输入: head = [1,2,3,4,5]
输出: [5,4,3,2,1]

image.png

输入: head = [1,2]
输出: [2,1]

迭代

假设链表为 1 -> 2 ->3 1→2→3→∅,我们想要把它改成  1<-2<-3∅←1←2←3。

在遍历链表时,将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点,因此必须事先存储其前一个节点。在更改引用之前,还需要存储后一个节点。最后返回新的头引用。

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

双指针

定义两个指针: prepre 和 curcur ;prepre 在前 curcur 在后。 每次让 prepre 的 nextnext 指向 curcur ,实现一次局部反转 局部反转完成之后,prepre 和 curcur 同时往前移动一个位置 循环上述过程,直至 prepre 到达链表尾部

class Solution {
  public ListNode reverseList(ListNode head) {
    //申请节点,pre和 cur,pre指向null
    ListNode pre = null;
    ListNode cur = head;
    ListNode tmp = null;
    while(cur!=null) {
      //记录当前节点的下一个节点
      tmp = cur.next;
      //然后将当前节点指向pre
      cur.next = pre;
      //pre和cur节点都前进一位
      pre = cur;
      cur = tmp;
    }
    return pre;
  }
}

结束

好了,我们的双指针也差不多了,我们明天开始刷其他的了,大家继续加油,我是小六六,三天打鱼,两天晒网!

目录
打赏
0
0
0
0
11
分享
相关文章
|
9月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
100 1
|
11月前
【bug记录】旋转链表与力扣报错:member access within null pointer of type ‘struct ListNode‘
【bug记录】旋转链表与力扣报错:member access within null pointer of type ‘struct ListNode‘
180 0
【算法】——双指针算法合集(力扣)
移动零,复写零,快乐数,盛最多水的容器,有效三角形的个数,和为s的两个数(查找总价格为目标值的两个商品 ),三数之和,四数之和
【链表】算法题(二) ----- 力扣/牛客
【链表】算法题(二) ----- 力扣/牛客
|
9月前
|
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
203 0
|
9月前
|
一篇文章了解区分指针数组,数组指针,函数指针,链表。
一篇文章了解区分指针数组,数组指针,函数指针,链表。
66 0
【链表】算法题(一) ----- 力扣 / 牛客
【链表】算法题(一) ----- 力扣 / 牛客
|
11月前
|
【Leetcode刷题Python】138. 复制带随机指针的链表
LeetCode上题目“138. 复制带随机指针的链表”的Python解决方案,包括两种方法:一种是在每个节点后复制一个新节点然后再分离出来形成新链表;另一种是构建一个字典来跟踪原始节点与其副本之间的映射关系,从而处理新链表的构建。
67 1
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问