专栏首页全部文章Day15:反转链表

Day15:反转链表

剑指Offer_编程题——反转链表

题目描述:

输入一个链表,反转链表后,输出新链表的表头。

具体要求:

时间限制: C/C++ 1秒,其他语言2秒 空间限制: C/C++32M,其他语言64M

具体思路:

背景知识介绍   在做本题之前首先介绍一下链表的基本知识。在维基百科中,链表 是这样定义的:链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表相应的时间复杂度分别是O(logn)和O(1)。一个链表如图所示:

  链表的基本元素有:节点:每个节点有两个部分,左边部分称为值域,用来存放用户数据;右边部分称为指针域,用来存放指向下一个元素的指针。head:head节点永远指向第一个节点;tail: tail永远指向最后一个节点;None:链表中最后一个节点的指针域为None值。 具体解题思路:   既然我们知道了链表相关的基本知识,那么要做到反转链表,我们应该将前一个节点与后一个节点断开,然后让前一个节点指向后一个节点,这个过程我们需要用到节点的引用来确定记录当前节点的前一个节点和后一个节点。这个思路的具体用java代码实现如下:

public class Solution{
	public ListNode ReverseList(ListNode head){
	    if(head == null)
	    	return null;
	    ListNode pre = null;
	    ListNode next = null;
	    while(head != null){
	    	next = head.next;
	    	head.next = pre;
	    	pre = head;
	    	head = next;
	    }
	    	return pre;
	}
}

代码效果图如图所示:

  正如上一篇提到一样,牛客网已经为我们定义了节点,不需要我们重复定义,但是在自己的本地编译器中,我们需要定义节点ListNode的类,具体实现如下:

public class ListNide{
	int val;
	ListNode next = null;
	ListNode(int val){
		this.val = val;
	}
}

当然我们也可以用python来实现上面这一思路:

class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        if not pHead or not pHead.next:
            return pHead
        last = None
        while pHead:
            tmp = pHead.next
            pHead.next = last
            last = pHead
            pHead = tmp
        return last

代码效果图如图所示:

用python定义的节点如下:

class ListNode:
	def __init__(self, x):
		self.val = x
		self.next = None

总结

  本道题主要考察链表的反转,在做此题之前我们应该了解链表的基本知识,再次基础上用多种自己掌握的语言实现它,力求做到融会贯通,其实这道题的难点在于如何用代码实现链表节点的断裂以及要保存前一个节点和后一个节点在断裂之前。另外我们用python语言实现时,如果直接用list[:: -1]就不太方便。总之,继续加油,争取早日找到工作,Good Luck!!!

参考文献

  本文的代码主要参考以下文章: [1] 维基百科·链表 [2] flyingsen [3] 试着去听歌 [4] 黄小猿

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Day26:二叉搜索树与双向链表

    背景知识介绍   在做该题之前,我们应该首先了解二叉搜索树,详细解释请看本文。接下来,还需要我们了解二叉树的中序遍历,因为我们做本题最关键的思想就是二叉树的中...

    stefan666
  • Day 3:从尾到头打印链表

    思路1: 1、先构造一个链表 2、定义一个栈,将链表元素放入到栈中 3、利用栈的先进后出,实现从尾到头返回 4、取出栈中元素放入到ArrayList,然...

    stefan666
  • Day55:链表中环的入口结点

    链表中有环证明   首先在做题之前我们要证明一个链表是否存在环,这里我们用到的就是——快慢指针法。首先给大家介绍两个快慢指针的结论: 1、设置快慢指针,假如...

    stefan666
  • 5.链表导论-心法篇

    链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以...

    码哥字节
  • 23张图!万字详解「链表」,从小白到大佬!

    链表和数组是数据类型中两个重要又常用的基础数据类型,数组是连续存储在内存中的数据结构,因此它的优势是可以通过下标迅速的找到元素的位置,而它的缺点则是在插入和删除...

    Java中文社群_老王
  • LeetCode 142:环形链表 II Linked List Cycle II

    为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。

    爱写bug
  • 新手React开发人员做错的5件事

    请勿执行的操作以及如何解决的方法,这部分内容是针对React的新手开发人员提供的。

    Dunizb
  • 数据结构|实现一个链表[4]

    如上面的代码,就是构建了链表在内存中的存储结构,int data是需要存储的int数据。struct JD *prior则是定义指向前面一个链表结构体的指针。s...

    Rare0716
  • LeetCode 142:环形链表 II Linked List Cycle II

    为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

    爱写bug
  • 使用JS生成Audio元素

    https://developer.mozilla.org/en-US/docs/Web/API/HTMLAudioElement

    山河木马

扫码关注云+社区

领取腾讯云代金券