2018-07-26

合并有顺序的数组

package main

import "fmt"

func main() {
    c := mergeTwoSortedArrays([]int{1, 5, 9}, []int{2, 6})
    fmt.Println(c)
}

func mergeTwoSortedArrays(a []int, b []int) []int {
    var i, j int
    c := make([]int, 0, len(a)+len(b))
    for i < len(a) && j < len(b) {
        if a[i] < b[j] {
            c = append(c, a[i])
            i++
        } else {
            c = append(c, b[j])
            j++
        }
    }
    if i < len(a) {
        c = append(c, a[i:]...)
    }
    if j < len(b) {
        c = append(c, b[j:]...)
    }
    return c
}

打印两个有序链表的公共部分

package main

import "fmt"

func main() {
    head1 := &Node{
        1,
        &Node{
            2,
            &Node{
                3,
                nil,
            },
        },
    }
    head2 := &Node{
        2,
        &Node{
            3,
            nil,
        },
    }
    printCommonPart(head1, head2)

}

type Node struct {
    Value int
    Next  *Node
}

func printCommonPart(head1 *Node, head2 *Node) {
    fmt.Println("Common Part: ")
    for head1 != nil && head2 != nil {
        if head1.Value < head2.Value {
            head1 = head1.Next
        } else if head1.Value > head2.Value {
            head2 = head2.Next
        } else {
            fmt.Println(head1.Value)
            head1 = head1.Next
            head2 = head2.Next
        }
    }
}

在单链表和双链表中删除倒数第k个节点

1. 单链表

package main

import "fmt"

func main() {
    head1 := &Node{
        1,
        &Node{
            2,
            &Node{
                3,
                nil,
            },
        },
    }
    head := removeLastKthNode(head1, 2)
    fmt.Println(*head, *head.Next)
}

type Node struct {
    Value int
    Next  *Node
}

func removeLastKthNode(head *Node, lastKth int) *Node {
    if head == nil || lastKth < 1 {
        return head
    }
    cur := head
    for cur != nil {
        lastKth--
        cur = cur.Next
    }
    if lastKth == 0 {
        head = head.Next
    }
    if lastKth < 0 {
        cur := head
        for lastKth+1 != 0 {
            lastKth++
            cur = cur.Next
        }
        cur.Next = cur.Next.Next
    }
    return head

}

2. 双链表

package main

import "fmt"

func main() {
    head := removeLastKthNode(nil, 2)
    fmt.Println(*head, *head.Next)
}

type Node struct {
    Value int
    Next  *Node
    Last  *Node
}

func removeLastKthNode(head *Node, lastKth int) *Node {
    if head == nil || lastKth < 1 {
        return head
    }
    cur := head
    for cur != nil {
        lastKth--
        cur = cur.Next
    }
    if lastKth == 0 {
        head = head.Next
    }
    if lastKth < 0 {
        cur := head
        for lastKth+1 != 0 {
            lastKth++
            cur = cur.Next
        }
        newNext := cur.Next.Next
        cur.Next = newNext
        if newNext != nil {
            newNext.Last = cur
        }
    }
    return head

}

删除链表的中间节点

package main

import "fmt"

func main() {
    head1 := &Node{
        1,
        &Node{
            2,
            &Node{
                3,
                nil,
            },
        },
    }
    r := removeMidNode(head1)
    fmt.Println(*r,r.Next)
}

type Node struct {
    Value int
    Next  *Node
}

func removeMidNode(head *Node) *Node {
    if head == nil || head.Next == nil {
        return head
    }
    if head.Next.Next == nil {
        return head.Next
    }
    pre := head
    cur := head.Next.Next
    for cur.Next != nil && cur.Next.Next != nil {
        pre = pre.Next
        cur = cur.Next.Next
    }
    pre.Next = pre.Next.Next
    return head
}

删除链表的a/b处的节点

• 即删除a*n/b 向上取整

package main

import (
    "fmt"
    "math"
)

func main() {
    head1 := &Node{
        1,
        &Node{
            2,
            &Node{
                3,
                nil,
            },
        },
    }
    r := removeByRatio(head1, 1, 3)
    fmt.Println(*r, r.Next)
}

type Node struct {
    Value int
    Next  *Node
}

func removeByRatio(head *Node, a int, b int) *Node {
    if a < 1 || a > b {
        return head
    }
    n := 0
    cur := head
    for cur != nil {
        n++
        cur = cur.Next
    }
    k := math.Ceil(float64(n * a / b))
    if k == 1 {
        return head.Next
    }
    if k > 1 {
        cur := head
        for k != 1 {
            k--
            cur = cur.Next
        }
        cur.Next = cur.Next.Next
    }
    return head
}

反转单向表

package main

import (
    "fmt"
)

func main() {
    head1 := &Node{
        1,
        &Node{
            2,
            &Node{
                3,
                nil,
            },
        },
    }
    r := reverselist(head1)
    fmt.Println(*r, r.Next)
}

type Node struct {
    Value int
    Next  *Node
}

func reverselist(head *Node) *Node {
    var pre *Node
    var next *Node
    for head != nil {
        next = head.Next
        head.Next = pre
        pre = head
        head = next
    }
    return pre
}

反转双向链表

package main

type Node struct {
    Value int
    Next  *Node
    Last  *Node
}

func reverselist(head *Node) *Node {
    var pre *Node
    var next *Node
    for head != nil {
        next = head.Next
        head.Next = pre
        head.Last = next
        pre = head
        head = next
    }
    return pre
}