【LeetCode】21. 2つの順序付きチェーンテーブルを結合

文書ディレクトリ

一、題名説明

二、テーマ分析

三、コード実装

一、テーマの説明
2つの順序付きチェーンテーブルを新しい順序付きチェーンテーブルに結合して返します.新しいチェーンテーブルは、指定された2つのチェーンテーブルのすべてのノードを接合することによって構成されます.
例:

  ：1->2->4, 1->3->4
  ：1->1->2->3->4->4

二、テーマ分析
まず、チェーンテーブルはすべて秩序化されたチェーンテーブルであり、ソートの問題を考慮する必要はありません.今はチェーンテーブル要素とマージの問題を比較するだけです.チェーンヘッダーから2つのチェーンテーブルの要素サイズを順番に比較し、新しいチェーンテーブルに配置すれば、新しいチェーンテーブルノードを再作成し、新しいチェーンテーブル空間を返すことができます.また、古いチェーンテーブルのノードを利用して、ポインタの指向を変更し、新しいチェーンテーブルに組み合わせることができます.
注意点:

入力はすべて空の

である可能性がある.

ローカル変数初期化

値サイズの比較

三、コード実装

// leetcode_21.         
//         

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

//     ListNode
func initList(val int) *ListNode {
	return &ListNode{val, nil}
}

//    Node
func appendNode(ln *ListNode, val int) {
	tmp := ln
	if tmp == nil {
		tmp = &ListNode{val, nil}
		return
	}
	for tmp.Next != nil {
		tmp = tmp.Next
	}
	tmp.Next = &ListNode{val, nil}
}

//    List
func appendNodeList(ln *ListNode, node *ListNode) {
	tmp := ln
	if tmp == nil {
		tmp = node
		return
	}
	for tmp.Next != nil {
		tmp = tmp.Next
	}
	tmp.Next = node
}

//               List
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	tmp1 := l1
	tmp2 := l2
	tmp3 := new(ListNode)
	tmp3_tmp := tmp3

	for tmp1 != nil && tmp2 != nil {
		if tmp1.Val < tmp2.Val {
			tmp3_tmp.Next = tmp1
			tmp1 = tmp1.Next
		} else {
			tmp3_tmp.Next = tmp2
			tmp2 = tmp2.Next
		}
		tmp3_tmp = tmp3_tmp.Next
	}

	if tmp1 == nil {
		tmp3_tmp.Next = tmp2
	} else if tmp2 == nil {
		tmp3_tmp.Next = tmp1
	}

	return tmp3.Next
}

//          
func mergeTwoLists1(l1 *ListNode, l2 *ListNode) *ListNode {
	tmp1 := l1
	tmp2 := l2
	tmp_val := 0
	tmp3 := new(ListNode)

	for tmp1 != nil && tmp2 != nil {
		if tmp1.Val < tmp2.Val {
			tmp_val = tmp1.Val
			tmp1 = tmp1.Next
		} else {
			tmp_val = tmp2.Val
			tmp2 = tmp2.Next
		}
		appendNode(tmp3, tmp_val)
	}

	if tmp1 == nil {
		appendNodeList(tmp3, tmp2)
	} else if tmp2 == nil {
		appendNodeList(tmp3, tmp1)
	}

	return tmp3.Next
}

//     
func (ln *ListNode) printList() {
	fmt.Printf("list: ")
	for tmp := ln; tmp != nil; tmp = tmp.Next {
		fmt.Printf("%d->", tmp.Val)
	}
	fmt.Printf("nil
")
}

func main() {
	l1 := initList(1)
	l2 := initList(1)

	appendNode(l1, 2)
	appendNode(l1, 4)
	appendNode(l2, 3)
	appendNode(l2, 4)
	l1.printList()
	l2.printList()

	l3 := mergeTwoLists(l1, l2)
	//l3 := mergeTwoLists(nil, nil)
	l3.printList()
}

実行結果:

list: 1->2->4->nil
list: 1->3->4->nil
list: 1->1->2->3->4->4->nil

Process finished with exit code 0

——2019-09-01——