代码随想录训练营第三天| 203.移除链表元素、206.反转链表

2023-12-25 09:23:15

203.移除链表元素

题目

力扣题目链接

思路(设置一个虚拟头结点再进行删除操作

这里以链表 1 4 2 4 来举例,移除元素4。

可以设置一个虚拟头结点,这样原链表的所有节点就都可以按照统一的方式进行移除了。

来看看如何设置一个虚拟头。依然还是在这个链表中,移除元素1。

最后呢在题目中,return 头结点的时候,别忘了?return dummyHead.next;, 这才是新的头结点。

代码如下(JavaScript)

var removeElements = function(head, val) {
    const dummyHead =new ListNode(0,head)  //创建虚拟头节点
    let cur =dummyHead    //设置一个当前指针指向虚拟头节点
    while(cur.next){   //cur.next不为空时,就是 指针还未到达最后一个节点时,执行循环
        if(cur.next.val===val){
            cur.next=cur.next.next   //移除节点
            continue
        }
        cur=cur.next   //移动指针
    }
    return dummyHead.next   //返回新的头节点

};

?206.反转链表

题目

力扣题目链接

题意:反转一个单链表。

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

思路

如果再定义一个新的链表,实现链表元素的反转,其实这是对内存空间的浪费。

其实只需要改变链表的next指针的指向,直接将链表反转 ,而不用重新定义一个新的链表,如图所示:

?

之前链表的头节点是元素1, 反转之后头结点就是元素5 ,这里并没有添加或者删除节点,仅仅是改变next指针的方向?

代码如下(JavaScript)

双指针法

 var reverseList = function(head) {
        let cur=head    //在头节点定义一个指针
        let pre=null    //在cur指针之前定义一个pre指针
        let temp=null   //定义一个临时指针
        while(cur){     
        temp = cur.next  //先将cur.next所指向的节点暂时存放在temp上
        cur.next=pre     //将cur指针的指向调转方向,指向pre
        //将pre和cur朝着旧链表的尾节点方向移动
        pre=cur          
        cur=temp
        }
        return pre //最后pre指向新链表的头节点,所以返回pre
  };

递归法

//可以参照双指针法,有利于理解递归法的操作
//先构建一个函数,等会儿直接在reverseList中调用就行
var reverse = function (cur, pre) {  //cur初始化为head,pre初始化为null
    let temp = null
    if (cur===null) return pre  //当cur===null时,即链表反转结束,返回新链表的头节点
    temp = cur.next     //先将cur.next的值暂时存放在temp中
    cur.next = pre      //调转cur的箭头指向,指向pre
    //前面已完成第一次反转,接着继续调用reverse函数,继续反转下去,即继续递归下去,直到cur===null,停止指针移动
    return reverse(temp, cur)    
}
var reverseList = function (head) {
    return reverse(head, null)
};  

文章来源:https://blog.csdn.net/weixin_61498310/article/details/132788768
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。