文档章节

单链表翻转 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

没有更多内容

加载失败,请刷新页面

加载更多

一个可能的NEO链上安全随机数解决方案

0x00 困境 链上安全随机数生成应该算是一个比较蛋疼的问题,哪怕你的系统再牛逼,合约程序困在小小的虚拟机里,哪怕天大的本事也施展不开。 更悲催的是,交易执行的时候,是在每一个节点都执...

暖冰
54分钟前
1
0
【大福利】极客时间专栏返现二维码大汇总

我已经购买了如下专栏,大家通过我的二维码你可以获得一定额度的返现! 然后,再给大家来个福利,只要你通过我的二维码购买,并且关注了【飞鱼说编程】公众号,可以加我微信或者私聊我,我再...

飞鱼说编程
今天
1
0
Spring5对比Spring3.2源码之容器的基本实现

最近看了《Spring源码深度解析》,该书是基于Spring3.2版本的,其中关于第二章容器的基本实现部分,目前spring5的实现方式已有较大改变。 Spring3.2的实现: public void testSimpleLoad(){...

Ilike_Java
今天
1
0
【王阳明心学语录】-001

1.“破山中贼易,破心中贼难。” 2.“夫万事万物之理不外于吾心。” 3.“心即理也。”“心外无理,心外无物,心外无事。” 4.“人心之得其正者即道心;道心之失其正者即人心。” 5.“无...

卯金刀GG
今天
2
0
OSChina 周三乱弹 —— 我们无法成为野兽

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @ _刚刚好: 霸王洗发水这波很骚 手机党少年们想听歌,请使劲儿戳(这里) hahahahahahh @嘻酱:居然忘了喝水。 让你喝可乐的话, 你准忘不了...

小小编辑
今天
12
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部