剑指offer刷题 - day02

JZ25 合并两个排序的链表

迭代实现

package main


import . "nc_tools"

/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param pHead1 ListNode类
 * @param pHead2 ListNode类
 * @return ListNode类
 */
func Merge(pHead1 *ListNode, pHead2 *ListNode) *ListNode {
    if pHead1 == nil {
        return pHead2
    }
    if pHead2 == nil {
        return pHead1
    }
    var head *ListNode = &ListNode{}
    p := head
    for pHead1 != nil && pHead2 != nil {
        if pHead1.Val >= pHead2.Val {
            p.Next = pHead2
            p = p.Next
            pHead2 = pHead2.Next
        } else {
            p.Next = pHead1
            p = p.Next
            pHead1 = pHead1.Next
        }
    }
    if pHead1 != nil {
        p.Next = pHead1
    } else if pHead2 != nil {
        p.Next = pHead2
    }
    return head.Next
}

递归实现

package main


import . "nc_tools"

/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param pHead1 ListNode类
 * @param pHead2 ListNode类
 * @return ListNode类
 */
func Merge(pHead1 *ListNode, pHead2 *ListNode) *ListNode {
    if pHead1 == nil {
        return pHead2
    }
    if pHead2 == nil {
        return pHead1
    }
    if pHead1.Val >= pHead2.Val {
        pHead2.Next = Merge(pHead1, pHead2.Next)
        return pHead2
    } else {
        pHead1.Next = Merge(pHead1.Next, pHead2)
        return pHead1
    }
}

JZ52 两个链表的第一个公共结点

这题没做出来，看了大佬的题解和官方的题解

使用 双指针解法，让两个链表走相同的长度，相等的速度，当 pHead1==pHead2 时就是结果，即使没有相同的公共节点，最后走完，两个都是 nil 也是相等的，使两个链表一定等长让 pHead1+pHead2==pHead2+pHead1 就好了，使用循环实现，下面这个是大佬分享的动态图，可以很清晰明了的明白。

package main

import . "nc_tools"

/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 *
 * @param pHead1 ListNode类
 * @param pHead2 ListNode类
 * @return ListNode类
 */
func FindFirstCommonNode(pHead1 *ListNode, pHead2 *ListNode) *ListNode {
    h1, h2 := pHead1, pHead2
    for h1 != h2 {
        if h1 == nil {
            h1 = pHead1
        } else {
            h1 = h1.Next
        }
        if h2 == nil {
            h2 = pHead2
        } else {
            h2 = h2.Next
        }
    }
    return h1
}