Python 数据结构之旋转链表

2024-12-22 15:08:11

题目描述：给定一个链表，旋转链表，使得每个节点向右移动k个位置，其中k是一个非负数

样例：给出链表1->2->3->4->5->null和k=2；返回4->5->1->2->3->null

首先，观察一下这个题目要达到的目的，其实，换一种说法，可以这样来描述：给出一个k值，将链表从倒数第k个节点处起之后的部分移动到链表前面，就样例来说，其实是将4->5这一部分移动到整个链表前面，变成4->5->1->2->3->null。不过，需要注意的是，题中没有给出k的大小，当k比链表的长度还大的时候，我们就需要先用k对链表的长度求余，比如，如果k = 7，那么上面的例子还是将4->5移动到整个链表前面。

所以说，这个题的思路可以这样来总结：

1. 先求出整个链表的长度
2. 根据k值找到需要移动的部分链表的前驱（样例中的3）
3. 在前驱之后将链表断开，移动后半部分

代码如下：

# Definition for singly-linked list.
# class ListNode:
#   def __init__(self, x):
#     self.val = x
#     self.next = None 

class Solution:
  # @param head: the list
  # @param k: rotate to the right k places
  # @return: the list after rotation
  def rotateRight(self, head, k):
    if head is None:
      return head
    cur = head
    count = 1
    # 计算链表长度
    while cur.next:
      cur = cur.next
      count += 1
    # 为节省代码量，这里是一个很有技巧的处理：用尾节点链接头结点
    cur.next = head
    # 此处，k为cur从尾节点到要断开部分的前驱需走的步数
    k = count - k % count
    # 找到前驱
    while k != 0:
      cur = cur.next
      k -= 1
    # 断开
    head = cur.next
    cur.next = None
    # 因为首尾已经相连，所以直接返回前驱后面的那个节点即可，此处引用为head
    return head
    # write your code here

需要注意的是21行首尾相连的技巧，这大大节省了我们的代码量，其实，就按之前思路中所描述的一步步来，也没问题。但是这个技巧确实很棒，值得学习。具体的细节我写在了代码注释里。

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

python数据结构链表之单向链表(实例讲解)

单向链表单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域(元素域)和一个链接域.这个链接指向链表中的下一个节点,而最后一个节点的链接域则指向一个空值. 表元素域elem用来存放具体的数据. 链接域next用来存放下一个节点的位置(python中的标识) 变量p指向链表的头节点(首节点)的位置,从p出发能找到表中的任意节点. 节点实现 class Node(object): """单链表的结点""" def __i
python单链表实现代码实例

链表的定义:链表(linked list)是由一组被称为结点的数据元素组成的数据结构,每个结点都包含结点本身的信息和指向下一个结点的地址.由于每个结点都包含了可以链接起来的地址信息,所以用一个变量就能够访问整个结点序列.也就是说,结点包含两部分信息:一部分用于存储数据元素的值,称为信息域:另一部分用于存储下一个数据元素地址的指针,称为指针域.链表中的第一个结点的地址存储在一个单独的结点中,称为头结点或首结点.链表中的最后一个结点没有后继元素,其指针域为空. python单链表实现代码: 复制代码
Python数据结构与算法之链表定义与用法实例详解【单链表、循环链表】

本文实例讲述了Python数据结构与算法之链表定义与用法.分享给大家供大家参考,具体如下: 本文将为大家讲解: (1)从链表节点的定义开始,以类的方式,面向对象的思想进行链表的设计 (2)链表类插入和删除等成员函数实现时需要考虑的边界条件, prepend(头部插入).pop(头部删除).append(尾部插入).pop_last(尾部删除) 2.1 插入: 空链表链表长度为1 插入到末尾 2.2 删除空链表链表长度为1 删除末尾元素 (3)从单链表到单链表的一众变体: 带尾节点的单链表
Python实现的数据结构与算法之链表详解

本文实例讲述了Python实现的数据结构与算法之链表.分享给大家供大家参考.具体分析如下: 一.概述链表(linked list)是一组数据项的集合,其中每个数据项都是一个节点的一部分,每个节点还包含指向下一个节点的链接. 根据结构的不同,链表可以分为单向链表.单向循环链表.双向链表.双向循环链表等.其中,单向链表和单向循环链表的结构如下图所示: 二.ADT 这里只考虑单向循环链表ADT,其他类型的链表ADT大同小异.单向循环链表ADT(抽象数据类型)一般提供以下接口: ① SinCycLin
Python二叉搜索树与双向链表转换实现方法

本文实例讲述了Python二叉搜索树与双向链表实现方法.分享给大家供大家参考,具体如下: # encoding=utf8 ''' 题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表. 要求不能创建任何新的结点,只能调整树中结点指针的指向. ''' class BinaryTreeNode(): def __init__(self, value, left = None, right = None): self.value = value self.left = left self.
Python 实现链表实例代码

Python 实现链表实例代码前言算法和数据结构是一个亘古不变的话题,作为一个程序员,掌握常用的数据结构实现是非常非常的有必要的. 实现清单实现链表,本质上和语言是无关的.但是灵活度却和实现它的语言密切相关.今天用Python来实现一下,包含如下操作: ['addNode(self, data)'] ['append(self, value)'] ['prepend(self, value)'] ['insert(self, index, value)'] ['delNode(self,
Python数据结构之翻转链表

翻转一个链表样例:给出一个链表1->2->3->null,这个翻转后的链表为3->2->1->null 一种比较简单的方法是用"摘除法".就是先新建一个空节点,然后遍历整个链表,依次令遍历到的节点指向新建链表的头节点. 那样例来说,步骤是这样的: 1. 新建空节点:None 2. 1->None 3. 2->1->None 4. 3->2->1->None 代码就非常简单了: """
python双向链表实现实例代码

示意图: python双向链表实现代码: 复制代码代码如下: #!/usr/bin/python# -*- coding: utf-8 -*- class Node(object): def __init__(self,val,p=0): self.data = val self.next = p self.prev = p class LinkList(object): def __init__(self): self.he
Python单链表的简单实现方法

本文实例讲述了Python单链表的简单实现方法,分享给大家供大家参考.具体方法如下: 通常来说,要定义一个单链表,首先定义链表元素:Element.它包含3个字段: list:标识自己属于哪一个list datum:改元素的value next:下一个节点的位置具体实现代码如下: class LinkedList(object): class Element(object): def __init__(self,list,datum,next): self._list = list self.
python数据结构之链表的实例讲解

在程序中,经常需要将⼀组(通常是同为某个类型的)数据元素作为整体管理和使⽤,需要创建这种元素组,⽤变量记录它们,传进传出函数等. ⼀组数据中包含的元素个数可能发⽣变化(可以增加或删除元素). 对于这种需求,最简单的解决⽅案便是将这样⼀组元素看成⼀个序列,⽤元素在序列⾥的位置和顺序,表示实际应⽤中的某种有意义的信息,或者表示数据之间的某种关系. 这样的⼀组序列元素的组织形式,我们可以将其抽象为线性表.⼀个线性表是某类元素的⼀个集合,还记录着元素之间的⼀种顺序关系.线性表是最基本的数据结构

Python 数据结构之旋转链表

相关推荐

随机推荐