首页 > 其他 > 详细

【LeetCode】206.反转链表

时间:2021-05-17 22:03:42      阅读:18      评论:0      收藏:0      [点我收藏+]

206.反转链表

知识点:链表;双指针;

题目描述

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

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

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

输入:head = []
输出:[]

解法一:双指针

将链表反转,就是把箭头的顺序换一下就可以了,可以采用双指针的方法,让cur的next为pre,然后pre和cur逐渐遍历,直到最后;

/**
 * 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){
            ListNode temp = cur.next;
            cur.next = pre;  //指向前一节点;
            pre = cur;      //两个指针依次后移;
            cur = temp;
        }
        return pre;
    }
}

时间复杂度:O(N);

体会

链表的题一般都需要定义虚头,并且格外关注前一节点和后一节点。

【LeetCode】206.反转链表

原文:https://www.cnblogs.com/Curryxin/p/14777224.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!