链表06--两个链表的第一个公共节点

链表06--两个链表的第一个公共节点-jz36

• ​​题目概述​​
• ​​解析&参考答案​​
• ​​注意事项​​
• ​​说明​​

题目概述

• 算法说明
  输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
• 测试用例
  输入：
  L1： p1(1)->p2(2)->p3(3)->p6(6)-p7(7)
  L2： p4(4)->p5(5)->p6(6)-p7(7)
  输出：
  p6(6)

解析&参考答案

• 解析
  方法1： 使用栈后进先出的思想，将节点分别放在2个栈，每次弹出一个，栈顶必然相同，当不同的时候其上一次弹出的即为公共节点；
  方法2： 分别计算2个链表长度，假设其差为k，则长链表先遍历k，然后同时遍历并比较节点是否相同，第一个相同的即为公共节点。
• 参考答案

vim jz36.go
package main

import (
"container/list"
"fmt"
)

type ListNode struct {
Val int
Next *ListNode
}

func GetLenList(head *ListNode) int {
if head == nil {
return 0
}
p := head
lenList := 0
for p != nil {
lenList++
p = p.Next
}
return lenList
}

func FindFirstCommonNode(pHead1 *ListNode, pHead2 *ListNode) *ListNode {
len1 := GetLenList(pHead1)
len2 := GetLenList(pHead2)
lenDiff := len1 - len2
p1 := pHead1
p2 := pHead2
if len1 < len2 {
p1 = pHead2
p2 = pHead1
lenDiff = len2 - len1
}
for i := 0; i < lenDiff; i++ {
p1 = p1.Next
}
var result *ListNode = nil
for p1 != nil {
if p1 == p2 {
result = p1
break
}
p1 = p1.Next
p2 = p2.Next
}
return result
}

func FindFirstCommonNodeV2(pHead1 *ListNode, pHead2 *ListNode) *ListNode {
if pHead1 == nil {
return pHead2
}
if pHead2 == nil {
return pHead1
}
l1 := list.New()
l2 := list.New()
p := pHead1
for p != nil {
l1.PushFront(p)
p = p.Next
}
p = pHead2
for p != nil {
l2.PushFront(p)
p = p.Next
}
var result *ListNode = nil
item1 := l1.Front()
item2 := l2.Front()
for item1 != nil && item2 != nil {
if item1.Value == item2.Value {
result = item1.Value.(*ListNode)
item1 = item1.Next()
item2 = item2.Next()
} else {
break
}
}
return result
}

func main() {
p1 := &ListNode{1, nil}
p2 := &ListNode{2, nil}
p3 := &ListNode{3, nil}
p4 := &ListNode{4, nil}
p5 := &ListNode{5, nil}
p6 := &ListNode{6, nil}
p7 := &ListNode{7, nil}
p1.Next, p2.Next, p3.Next, p4.Next, p5.Next, p6.Next, p7.Next = p2, p3, p6, p5, p6, p7, nil
ret := FindFirstCommonNodeV2(p1, p4)
fmt.Println(ret.Val)
}

注意事项

to add

说明

当前使用 go1.15.8

参考​​牛客网--剑指offer​​ 标题中jzn(n为具体数字)代表牛客网剑指offer系列第n号题目，例如 jz01 代表牛客网剑指offer中01号题目。

注意!!!

• 笔者最近在学习 golang，因此趁机通过数据结构和算法来进一步熟悉下go语言
• 当前算法主要来源于剑指 offer，后续会进一步补充 LeetCode 上重要算法，以及一些经典算法
• 此处答案仅为参考，不一定是最优解，欢迎感兴趣的读者在评论区提供更优解