文档章节

单链表翻转 Rotate List

smart_w
 smart_w
发布于 2016/01/28 12:33
字数 323
阅读 70
收藏 1

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

package main

import (
	"fmt"
)

type List struct {
	next *List
	data int
}

var Head = &List{}

func add_node(val int) {
	newnode := &List{data: val}
	if Head.next == nil {
		Head.next = newnode
	} else {
		newnode.next = Head.next
		Head.next = newnode
	}
}

func show_list() {
	tmp := Head.next
	for tmp != nil {

		fmt.Printf("%d ", tmp.data)
		tmp = tmp.next
	}
	fmt.Printf("\n")
}

/*从链表右边反转K位 O(k*N)
example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.
*/

func rotateRList(k int) bool {
	tmp := Head.next
	var node *List
	var nodelast *List

	var prenode *List

	for tmp != nil {
		tmp1 := tmp
		for i := k; i > 0; i-- {
			if tmp1.next == nil {
				node = tmp
				nodelast = tmp1
				goto rotate
			}
			if tmp1.next != nil {
				tmp1 = tmp1.next
			} else {
				break
			}
		}
		prenode = tmp
		tmp = tmp.next
	}

rotate:
	if node == nil || node == Head.next {
		return false
	}

	nodelast.next = Head.next
	Head.next = node
	prenode.next = nil

	return true

}

//遍历两遍链表 O(N)
func rotateRList2(k int) bool {
	tmp := Head.next
	listLen := 0

	for tmp != nil {
		listLen++
		tmp = tmp.next
	}

	if listLen <= k {
		return false
	}

	var prenode *List
	var node *List
	var nodelast *List

	tmp = Head.next

	var index = listLen - k + 1
	node = tmp
	for i := 1; i < index; i++ {
		prenode = node
		node = node.next
	}
	nodelast = node
	for nodelast.next != nil {
		nodelast = nodelast.next
	}

	nodelast.next = Head.next
	Head.next = node
	prenode.next = nil

	return true

}

func main() {
	add_node(1)
	add_node(5)
	add_node(6)
	add_node(10)

	show_list()

	/*rotateRList(2)
	show_list()*/

	rotateRList2(2)
	show_list()

}

输出结果:

10 6 5 1 
5 1 10 6

 

© 著作权归作者所有

共有 人打赏支持
smart_w
粉丝 31
博文 74
码字总数 23007
作品 0
武汉
程序员
61.Rotate List-Leetcode

debug遇到的问题 1.语法之指向指针成员 2.当k大于链表长度的情况下 拿到这题我首先想到的就是用快慢指针来解,快指针先走k步,然后两个指针一起走,当快指针走到末尾时,慢指针的下一个位置是...

analanxingde
01/16
0
0
Linked List相关的题

237. Delete Node in a Linked List 这题跟正常的书里的删链表某个节点区别是传入的参数,书里函数输入是要删的那个节点的前一个节点,这题里给的函数输入就是要删的那个节点。 /** Definiti...

wcybrain
2017/10/31
0
0
【算法系列 一】 Linked List

给定两个链表,分别表示两个非负整数。它们的数字逆序存储在链表中,且每个结点只存储一个数字,计算两个数的和,并且返回该链表(Leetcode 2)。 Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Outpu...

Hosee
2016/03/01
112
1
旋转单链表

原题   Given a list, rotate the list to the right by k places, where k is non-negative.   For example:   Given and ,   return . 题目大意   向右旋转一个单链表,旋转k个位......

一贱书生
2016/12/16
0
0
Redis源码分析(adlist)

源码版本: 源码位置: adlist.h : 数据结构定义。 adlist.c:函数功能实现。 一、adlist简介 Redis中的链表叫(A generic doubly linked list implementation 一个通用的双端链表实现),和普...

yangbodong22011
2017/11/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Java IO类库之PrintStreamWriter

* A <code>PrintStream</code> adds functionality to another output stream, * namely the ability to print representations of various data values * conveniently. Two other fea......

老韭菜
今天
0
0
qduoj~前端~二次开发~笔记

青岛大学qdu的onlinejudge是js的写的前端,框架是vue.js,在nodejs上部署运行,其实整体运行还是建立在docker的容器虚拟环境里,这里暂时不需要docker。安装环境是Ubuntu14-64bit 1.安装一大...

虚拟世界的懒猫
今天
6
0
ConcurrentHashMap源码解读

部分内容转自:http://jiabinyuan.xyz/#/app/archive/detail/25 内部结构 内部采用了segment结构,每一个segment相当于一个hashtable。看下面的结构图: 从图的结构我们可以了解到,Concurr...

edwardGe
今天
1
0
Ubuntu终端Tab键自动补全

打开 /etc/bash.bashrc,找到下列代码,取消注释。 #enable bash completion in interactive shells#if ! shopt -oq posix; then# if [-f /usr/share/bash-completion/bash_compl......

大熊猫
今天
0
0
polipo socks5代理转http代理

天朝的网络,哎~ 装个 yarn 都时而会卡 假设在SSlocal 已经装好运行的前提下,来安装设置 polipo sudo apt-get install polipo sudo vim /etc/polipo/config 追加下列配置内容,并保存 socksP...

纯洁徐
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部