LeetCode中级算法-链表
两数相加
[题目]
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
[输入]
(2 -> 4 -> 3) + (5 -> 6 -> 4)[返回]
7 -> 0 -> 8[解法]
每个链表使用一个指针，同时向前推进，需要注意数进位
[代码实现]
package main
import "fmt"
type Node struct {
Value int
Next *Node
}
func main() {
node12 := &Node{ Value: 10, Next: nil }
node11 := &Node{Value: 4, Next: node12}
node10 := &Node{Value: 1, Next: node11}
node02 := &Node{Value: 8, Next: nil}
node01 := &Node{Value: 5, Next: node02}
node00 := &Node{Value: 2, Next: node01}
result := computeResult(node00, node10)
printNodeList(result)
}
func computeResult(node1 *Node, node2 *Node) *Node {
jinwei := 0
var start *Node
var node *Node
for node1 != nil || node2 != nil || jinwei != 0 {
node1Value := 0
if node1 != nil {
node1Value = node1.Value
node1 = node1.Next
}
node2Value := 0
if node2 != nil {
node2Value = node2.Value
node2 = node2.Next
}
nodeValue := node1Value + node2Value + jinwei
jinwei = nodeValue / 10
nodeValue = nodeValue % 10
nodeTmp := &Node{Value: nodeValue, Next: nil}
if node == nil {
node = nodeTmp
start = node
} else {
node.Next = nodeTmp
node = node.Next
}
}
return start
}
func printNodeList(node *Node) {
for node != nil {
fmt.Print(node.Value, "->")
node = node.Next
}
fmt.Print("Nil")
fmt.Println("")
}奇偶链表
[题目]
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
[输入1]
1->2->3->4->5->NULL[返回1]
1->3->5->2->4->NULL[输入2]
2->1->3->5->6->4->7->NULL[返回2]
2->3->6->7->1->5->4->NULL[解法]
使用两个指针奇数链指针odd和偶数链指针even，遍历链表将原链表分割成两条：奇数链表、偶数链表，最后再将链表前后合并。
[代码实现]
package main
import "fmt"
type Node struct {
Value int
Next *Node
}
func main() {
node5 := &Node{ Value: 6, Next: nil }
node4 := &Node{ Value: 5, Next: node5 }
node3 := &Node{ Value: 4, Next: node4 }
node2 := &Node{ Value: 3, Next: node3 }
node1 := &Node{Value: 2, Next: node2}
node0 := &Node{Value: 1, Next: node1}
result := computeResult(node0)
printNodeList(result)
}
// odd是奇数链的数据
// even是偶数链的数据
func computeResult(head *Node) *Node {
evenHead := head.Next
even := evenHead
odd := head
// 下面的遍历最终形成了两条链
// odd是奇数位置上的链
// even是偶数位置上的链
for even != nil && even.Next != nil {
odd.Next = even.Next
odd = odd.Next
even.Next = odd.Next
even = even.Next
}
// 将两个链连在一起
odd.Next = evenHead
return head
}
func printNodeList(node *Node) {
for node != nil {
fmt.Print(node.Value, "->")
node = node.Next
}
fmt.Print("Nil")
fmt.Println("")
}相交链
[题目]
给出两个单向链，找出两个子链相交的位置
[示例1]
[示例2]
[示例3]
[解法1]
暴力算法，时间复杂度O(n * m)，使用两个指针遍历两个单向链表
[代码实现1]
func computeResult(node1 *Node, node2 *Node) bool {
jiaoCha := false
node1Index := node1
node2Index := node2
for node1Index != nil {
if jiaoCha {
break
}
// 注意对node1的新一轮的遍历开始之前
// 需要把node2的指针位置归位到链表的开头
node2Index = node2
for node2Index != nil {
if node1Index == node2Index {
jiaoCha = true
break
}
node2Index = node2Index.Next
}
node1Index = node1Index.Next
}
return jiaoCha
}[解法2]
首先遍历一个子链，并使用map来记录它的各个节点，遍历完之后，再遍历另外一个子链，看看有没有重合的节点。时间复杂度 O(m + n)
[代码实现2]
func computeResult2(node1 *Node, node2 *Node) bool {
filter := map[*Node]int {}
for node1 != nil {
filter[node1] = 1
node1 = node1.Next
}
for node2 != nil {
if _, exists := filter[node2]; exists {
return true
}
node2 = node2.Next
}
return false
}[代码测试]
package main
import "fmt"
type Node struct {
Value int
Next *Node
}
func main() {
node3 := &Node{Value: 12, Next: nil}
node2 := &Node{Value: 11, Next: node3}
// node1 是两个单向链的相交节点
node1 := &Node{Value: 10, Next: node2}
node21 := &Node{Value: 5, Next: node1}
node20 := &Node{Value: 4, Next: node21}
node12 := &Node{Value: 3, Next: node1}
node11 := &Node{Value: 2, Next: node12}
node10 := &Node{Value: 1, Next: node11}
result := computeResult(node10, node20)
fmt.Println("result:", result)
result2 := computeResult2(node10, node20)
fmt.Println("result2:", result2)
}本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2020-12-29，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读