链表
27 minute read ∼ Filed in : codingLinked-list related
type ListNode struct {
Val int
Next *ListNode
}
1[Medium]. Find the Duplicate Number
// 主要是把list和链表关联起来，首先有索引和值的关系，其次把值也当作索引
// 3,1,3,4,2 可以看作 以下对应关系
// 0 -> 3
// 1 -> 1
// 2 -> 3
// 3 -> 4
// 4 -> 2， 进而绘制成环
func findDuplicate(nums []int) int {
slow := 0
fast := 0
for {
slow = nums[slow]
fast = nums[nums[fast]]
fmt.Println(slow, fast)
if slow == fast {
break
}
}
// meet
slow = 0
for{
slow = nums[slow]
fast = nums[fast]
fmt.Println(slow, fast)
if slow == fast {
return slow
}
}
}
2[Easy]. Remove Duplicates from Sorted List
func deleteDuplicates(head *ListNode) *ListNode {
if head == nil{
return head
}
slow := head
fast := head.Next
// use slow.next to make sure last pair is checked.
for slow.Next!=nil{
if slow.Val != fast.Val{
fast = fast.Next
slow = slow.Next
}else{
fast = fast.Next
slow.Next = fast
}
}
return head
}
3[Medium]. Remove Duplicates from Sorted List II
func deleteDuplicates(head *ListNode) *ListNode {
if head == nil{
return head
}
// 设置假点和slow点
slow := &ListNode{-1, head}
dummy := slow
fast := head
// 记录重复的值
var dup *ListNode
for fast.Next!=nil{
// 如果和重复值相等，跳过
if dup !=nil && fast.Val == dup.Val{
fast = fast.Next
continue
}
// 更新重复值
if fast.Val == fast.Next.Val{
dup = fast
}else{
slow.Next = fast
slow = fast
fast = fast.Next
}
}
// check the last value
if dup !=nil && fast.Val == dup.Val{
slow.Next = nil
}else{
slow.Next = fast
}
return dummy.Next
}
4[Easy].Reverse Linked List
func reverseList(head *ListNode) *ListNode {
var dummy *ListNode = nil
slow := dummy
fast := head
for fast!=nil{
node := fast.Next
fast.Next = slow
slow = fast
fast = node
}
return slow
}
5[Medium].Reverse Linked List II
func reverseBetween(head *ListNode, left int, right int) *ListNode {
// 假点，位于head之前
var node = &ListNode{-1, head}
res := node
// 遍历假点，知道index等于left
index := 0
for index+1 < left{
node = node.Next
index++
}
// 反转后面的前N位，然后和当前假点相连
if head.Next!=nil{
node.Next = reverseFistN(node.Next, right-left+1)
}
return res.Next
}
func reverseFistN(fast *ListNode, n int) *ListNode{
var slow *ListNode = nil
//记录首位
head := fast
// 反转前N位，
index := 1
for fast!=nil && index <= n{
node := fast.Next
fast.Next = slow
slow = fast
fast = node
index ++
}
// 首位和n+1位相连
head.Next = fast
return slow
}
6[Hard].Reverse Nodes in k-Group
func reverseKGroup(head *ListNode, k int) *ListNode{
pre := &ListNode{0, head}
res := pre
for head != nil{
// 确定尾部，从0开始遍历
tail := pre
for i:=0; i < k;i++{
tail = tail.Next
if tail == nil{return res.Next}
}
// 截断当前sub-LinkedList
nextHead := tail.Next
tail.Next = nil
// 反转
tail = head
head = reverse(head)
// 相连接
pre.Next = head
tail.Next = nextHead
// 移动指针
pre = tail
head = nextHead
}
return res.Next
}
func reverse(head * ListNode) * ListNode{
var dummy *ListNode = nil
slow := dummy
fast := head
for fast!=nil{
node := fast.Next
fast.Next = slow
slow = fast
fast = node
}
return slow
}
7[Easy].Merge Two Sorted Lists
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
pre := &ListNode{0, nil}
res := pre
for l1!=nil && l2!=nil{
if l1.Val < l2.Val{
pre.Next = l1
l1 = l1.Next
}else{
pre.Next = l2
l2 = l2.Next
}
pre = pre.Next
}
if l1!=nil{
pre.Next = l1
}
if l2!=nil{
pre.Next = l2
}
return res.Next
}
8[Medium].Partition List
func partition(head *ListNode, x int) *ListNode {
dummy := &ListNode{}
slow := dummy
fast := dummy
node := head
var slowBegin *ListNode =nil
var fastBegin *ListNode =nil
// 依次构造2个不同的linked-list
for node!=nil{
if node.Val < x{
if slowBegin == nil{
slowBegin=node
}
slow.Next = node
slow = slow.Next
}else{
if fastBegin == nil{
fastBegin=node
}
fast.Next = node
fast = fast.Next
}
node = node.Next
}
// 首位相连
slow.Next = fastBegin
fast.Next = nil
if slowBegin==nil{return fastBegin}else{return slowBegin}
}
9[Medium].Sort List
//sort the linked list in O(n logn) time and O(1) memory
func sortList(head *ListNode) *ListNode {
// 检查head情况
if head==nil || head.Next==nil{
return head
}
if head.Next.Next==nil{
if head.Next.Val > head.Val{
return head
}else{
node := head.Next
head.Next = nil
node.Next = head
return node
}
}
// 找中点， O(n)
index := 1
trNode := head
for trNode != nil{
trNode = trNode.Next
index++
}
mid := index/2
// 根据中电均分链表
index = 1
trNode = head
var left *ListNode = head
var right *ListNode
for trNode != nil{
trNode = trNode.Next
index++
if mid == index{
right = trNode.Next
trNode.Next = nil
break
}
}
// 递归 对左右分别排序
l1 := sortList(left)
l2 := sortList(right)
// 每次递归，返回合并后的值
return mergeTwoLists(l1, l2)
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
pre := &ListNode{0, nil}
res := pre
for l1!=nil && l2!=nil{
if l1.Val < l2.Val{
pre.Next = l1
l1 = l1.Next
}else{
pre.Next = l2
l2 = l2.Next
}
pre = pre.Next
}
if l1!=nil{
pre.Next = l1
}
if l2!=nil{
pre.Next = l2
}
return res.Next
}
10[Medium]. Reorder List
func reorderList(head *ListNode) {
// 中点
length := 1
node := head
for node!=nil{
node = node.Next
length++
}
mid := length/2
// partition 链表
index := 1
node = head
var left *ListNode = node
var right *ListNode
for node!=nil{
node = node.Next
index++
if index == mid{
right = node.Next
node.Next = nil
break
}
}
// 反转右边的
right = reverse(right)
// 链接起来
var res = &ListNode{0, head}
for left!=nil && right !=nil{
res.Next = left
left = left.Next
res = res.Next
res.Next = right
right = right.Next
res = res.Next
}
if left!=nil{
res.Next = left
}
if right!=nil{
res.Next = right
}
}
func reverse(head *ListNode) *ListNode{
var dummy *ListNode = nil
slow := dummy
fast := head
for fast!=nil{
node := fast.Next
fast.Next = slow
slow = fast
fast = node
}
return slow
}
11[Easy].Linked List Cycle
// using O(1) (i.e. constant) memory?
// 快慢指针，相遇就有环
func hasCycle(head *ListNode) bool {
slow := head
fast := head
step := 0
for fast!=nil && fast.Next!=nil{
if step > 0 && slow==fast{
return true
}
fast = fast.Next.Next
slow = slow.Next
step ++
}
return false
}
12[Medium].Linked List Cycle II
func detectCycle(head *ListNode) *ListNode {
if head==nil || head.Next==nil{
return nil
}
slow := head
fast := head
step := 0
for fast!=nil && fast.Next!=nil{
if step > 0 && fast==slow{
break
}
slow = slow.Next
fast = fast.Next.Next
step ++
}
if fast==nil || fast.Next==nil{
return nil
}
slow = head
step = 1
for fast!=slow{
fast = fast.Next
slow = slow.Next
step ++
}
return slow
}
13[Easy].Palindrome Linked List
func isPalindrome(head *ListNode) bool {
if head.Next == nil || head == nil{
return true
}
// find middle
length := 1
node := head
for node!=nil{
node = node.Next
length ++
}
mid := length/2
// partition
node = head
index := 1
left := node
right := &ListNode{}
for node!=nil{
if index == mid{
right = node.Next
node.Next = nil
break
}
node = node.Next
index ++
}
// reverse right
right = reverse(right)
for left!=nil && right!=nil{
if left.Val!=right.Val{
return false
}
left = left.Next
right = right.Next
}
return true
}
func reverse(head *ListNode)*ListNode{
var slow *ListNode = nil
fast := head
for fast!=nil{
node := fast.Next
fast.Next = slow
slow = fast
fast = node
}
return slow
}
14[Medium].Copy List with Random Pointer
func copyRandomList(head *Node) *Node {
// key: 老链的节点，value： 新链的节点
mapper := make(map[*Node]*Node)
// 新list的头
copyHead := &Node{}
copyNode := copyHead
// 先复制，并且补充好next的值
node := head
for node!=nil{
newNode := &Node{node.Val, nil, nil}
copyNode.Next = newNode
copyNode = copyNode.Next
mapper[node] = newNode
node = node.Next
}
copyNode.Next = nil
// 再填充random
node = head
copyNode = copyHead.Next
for node!=nil{
copyNode.Random = mapper[node.Random]
copyNode = copyNode.Next
node = node.Next
}
return copyHead.Next
}
15[Medium].Design Linked List
// 双端链表
type DLinkList struct{
Val int
Pre *DLinkList
Next *DLinkList
}
func ConstructDLinkList() *DLinkList{
a := new(DLinkList)
return a
}
type MyLinkedList struct {
head *DLinkList
tail *DLinkList
length int
}
func Constructor() MyLinkedList {
ins := MyLinkedList{}
ins.head = nil
ins.tail = nil
ins.length = 0
return ins
}
func (this *MyLinkedList) Get(index int) int {
if this.length <= index{
return -1
}
cur := this.head
for i:=0; i<index; i++{
cur = cur.Next
}
return cur.Val
}
func (this *MyLinkedList) AddAtHead(val int) {
if this.head == nil{
// 如果头为空，那么意味着没初始化，尾一定为空
this.head=&DLinkList{val, nil, nil}
this.tail = this.head
}else{
// 刚初始化完，头尾相等，
if this.head == this.tail{
this.head = &DLinkList{val, nil, this.tail}
this.tail.Pre = this.head
}else{
// 正常的
newNode := &DLinkList{val, nil, this.head}
this.head.Pre = newNode
this.head = newNode
}
}
this.length++
}
func (this *MyLinkedList) AddAtTail(val int) {
if this.tail == nil{
this.tail=&DLinkList{val, nil, nil}
this.head = this.tail
}else{
if this.head == this.tail{
this.tail=&DLinkList{val, this.head, nil}
this.head.Next = this.tail
}else{
newNode := &DLinkList{val, this.tail, nil}
this.tail.Next = newNode
this.tail = newNode
}
}
this.length++
}
func (this *MyLinkedList) AddAtIndex(index int, val int) {
if this.length < index{
return
}
if this.length == index{
this.AddAtTail(val)
return
}
if index == 0{
this.AddAtHead(val)
return
}
cur := this.head
for i:=0; i<index; i++{
cur = cur.Next
}
newNode := &DLinkList{val, cur.Pre, cur}
cur.Pre.Next = newNode
cur.Pre = newNode
this.length++
}
func (this *MyLinkedList) DeleteAtIndex(index int) {
if this.length <= index{
return
}
cur := this.head
for i:=0; i<index; i++{
cur = cur.Next
}
if cur !=this.head && cur != this.tail{
cur.Pre.Next = cur.Next
cur.Next.Pre = cur.Pre
}
// 刚初始化完，头尾相等，头尾都检查一遍，更新各自的值
if cur == this.head{
this.head = this.head.Next
if this.head!=nil{
this.head.Pre = nil
}
}
if cur == this.tail{
this.tail = this.tail.Pre
if this.tail!=nil{
this.tail.Next = nil
}
}
this.length--
}
16[Medium].Odd Even Linked List
func oddEvenList(head *ListNode) *ListNode {
if head==nil || head.Next==nil{
return head
}
oddPointer := head
oddMark := oddPointer
evenPointer := head.Next
evenMark := evenPointer
// 必须一次遍历同时生成2个链表
cur := head.Next.Next
index := 3
for cur!=nil{
if index%2==1{
oddPointer.Next = cur
oddPointer = cur
}else{
evenPointer.Next = cur
evenPointer = cur
}
cur = cur.Next
index ++
}
evenPointer.Next = nil
oddPointer.Next = evenMark
return oddMark
}
17[Medium].Add Two Numbers
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
var node *ListNode = nil
var res *ListNode = nil
prev := 0
for l1!=nil || l2!=nil{
// 如果都存在
if l1!=nil && l2!=nil{
value := (l1.Val+l2.Val+ prev)%10
prev = (l1.Val+l2.Val+ prev)/10
newNode := &ListNode{value,nil}
if node == nil{
node = newNode
res = newNode
}else{
node.Next = newNode
node = node.Next
}
l1 = l1.Next
l2 = l2.Next
// 如果l1存在
}else if l1!=nil{
value := (l1.Val+ prev)%10
prev = (l1.Val+ prev)/10
newNode := &ListNode{value,nil}
if node == nil{
node = newNode
res = newNode
}else{
node.Next = newNode
node = node.Next
}
l1 = l1.Next
// 如果l2存在
}else{
value := (l2.Val+ prev)%10
prev = (l2.Val+ prev)/10
newNode := &ListNode{value,nil}
if node == nil{
node = newNode
res = newNode
}else{
node.Next = newNode
node = node.Next
}
l2 = l2.Next
}
}
//如果还有进位
if prev !=0{
newNode := &ListNode{prev,nil}
if node == nil{
node = newNode
res = newNode
}else{
node.Next = newNode
node = node.Next
}
}
return res
}
18[Medium].Rotate List
func rotateRight(head *ListNode, k int) *ListNode {
if head == nil{return head}
// 算长度
len := 1
node := head
for node.Next!=nil{
len += 1
node = node.Next
}
// 算绝对的反转次数
k = k%len
if k == 0{
return head
}
// 记录最后一个点和第一个要反转的点的index
lastNode := node
indexLast := len - k
//第二次遍历，找出要反转的点的前一个点
node = head
for index := 0; index+1<indexLast; index++{
node = node.Next
}
res := node.Next
node.Next = nil
lastNode.Next = head
return res
}
19[Medium].Add Two Numbers II