文档章节

单链表翻转 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
粉丝 32
博文 74
码字总数 23007
作品 0
武汉
程序员
私信 提问
61.Rotate List-Leetcode

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

analanxingde
2018/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

没有更多内容

加载失败,请刷新页面

加载更多

2019-1-16

2019-1-16 星期三 晴转霾 早饭:小面包+鸡蛋糕;午饭:馍+地三鲜;晚饭:; 6:50起床,因为媳妇说可能今天晚上去大雁塔那边吃饭,早上起来后洗了个澡(主要因为头发很油了)。 今天早上天气...

莱菔籽
19分钟前
0
0
localDate、localDateTime、localTime的使用

从前端接受的时候,localDate类型的数据要转换,加 @DateTimeFormat(pattern = "yyyy-MM-dd")

shimmerkaiye
26分钟前
1
0
1.二叉树

概念 二叉树(binary tree)是每个节点最多只有两个分支(即不存在分支度大于2的节点)的结构树。通常分支被称为“左子树”和“右子树”,左子树和右子树的位置不能随意颠倒。二叉树的第i层 ...

火拳-艾斯
29分钟前
3
0
java 线程

一、通过实现Runnable接口来创建线程 public class TestThread implements Runnable { public void run() { try { for (int i = 0; i < 10; i++) { ......

朝如青丝暮成雪
35分钟前
1
0
关于eclipse2017 import javax.servlet.jsp.tagext引入错误得问题

在eclipse中: 这个javax.servlet.jsp.tagext属于是tomcat相关jar包找到jsp-api.jar 在tomcat文件夹下边的lib文件夹中就有 如果项目中报错的话 把这个加入到项目中 在myeclipse中: 如下图,...

ZhangLG
49分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部