题解 |迭代的两种写法 #反转链表#

反转链表

https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca

迭代的写法也叫双指针的写法

写法一:不带头结点的头插法,将目标链表的尾节点后的结点作为新节点插入目标链表的第1个位置,即目标链表的首结点之前。

自己根据王道课程的单链表建立的那节视频提到的带头结点的头插法,想的不带头结点的头插法。

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null ){//处理空链表
            return null;
        }
        ListNode last = head;//使用last指针指(尾指针)向目标链表的头尾结点
        ListNode fist = last;//使用fist(首指针)指针指向目标链表的头首结点
        while(last.next != null){//当尾指针后面没有节点时,表示链表只有1个节点无需反转|链表反转完成
            ListNode newNode = last.next;//当尾指针后面有节点时,取尾指针后的节点
            last.next = newNode.next;
            newNode.next = fist;//将取出的节点插入链表的第1个位置,即fist前
            fist = newNode;//首指针指向新插入的节点
        }
        return fist;

    }
}

写法二:将当前节点的next反转指向前一个节点

实际上是将一个链表分成了两个链表。

  • pre为新链表的首结点,表示目标链表,初始为null。
  • curr为待处理链表的首结点,表示待处理链表。
  • 取curr链表的首结点,插入prev链表的第1个位置,重复此操作,直到curr链表为空时结束。

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

全部评论

相关推荐

06-20 17:42
东华大学 Java
凉风落木楚山秋:要是在2015,你这简历还可以月入十万,可惜现在是2025,已经跟不上版本了
我的简历长这样
点赞 评论 收藏
分享
06-15 20:57
已编辑
门头沟学院 Java
CARLJOSEPH...:年轻人有傲气很正常,但是建议工作前洗净傲气。 说实在的,什么奖学金什么奖项的都很一般。尊重你的老师,在有时间的时候去上课,真遇到走不开的事,请态度端正地向你的老师说明情况,请求请假。我相信任何一个有师德的老师都会允许的(我的老师就是这样)。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务