单链表翻转 Rotate List
单链表翻转 Rotate List
golang_yh 发表于2年前
单链表翻转 Rotate List
  • 发表于 2年前
  • 阅读 69
  • 收藏 1
  • 点赞 1
  • 评论 0

移动开发云端新模式探索实践 >>>   

摘要: LeetCode golang每天刷刷小算法

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 int = 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


  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 30
博文 69
码字总数 18162
×
golang_yh
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: