【算法】010、合并两个有序链表

【算法】010、合并两个有序链表

一、合并两个有序链表

1.1 思路

// go
package main

import (
	"fmt"
	"strconv"
)

type ListNode struct {
	Val  int
	Next *ListNode
}

func (n *ListNode) String() (ans string) {
	for ; n != nil; n = n.Next {
		ans += "=>"
		ans += strconv.Itoa(n.Val)
	}
	return
}

// 原则: 函数退出时, 不改变入参 l1 和 l2
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	}
	if l2 == nil {
		return l1
	}

	n1 := l1
	n2 := l2 // 后续只操作 n1 和 n2 即可

	var l *ListNode = nil
	if n1.Val < n2.Val {
		l = n1
		n1 = n1.Next
	} else {
		l = n2
		n2 = n2.Next
	}

	pre := l
	for n1 != nil && n2 != nil {
		if n1.Val < n2.Val {
			pre.Next = n1
			n1 = n1.Next
		} else {
			pre.Next = n2
			n2 = n2.Next
		}
		pre = pre.Next
	}

	if n1 != nil {
		pre.Next = n1
	}
	if n2 != nil {
		pre.Next = n2
	}

	return l
}

func main() {
	c := &ListNode{4, nil}
	b := &ListNode{2, c}
	l1 := &ListNode{1, b}

	f := &ListNode{4, nil}
	e := &ListNode{3, f}
	l2 := &ListNode{1, e}

	fmt.Println(l1)
	fmt.Println(l2)
	l := mergeTwoLists(l1, l2)
	fmt.Println(l)
}

1.2 多语言解法

$Cpp/Go/Python/Rust/Js/Ts$

// cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int val) : val(val), next(nullptr) {}
    ListNode(int val, ListNode *next) : val(val), next(next) {}
};

ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
{
    ListNode *n1 = l1;
    ListNode *n2 = l2;
    if (n1 == nullptr)
    {
        return n2;
    }
    if (n2 == nullptr)
    {
        return n1;
    }

    ListNode *dummy = new ListNode(0);
    ListNode *n = dummy;

    while (n1 != nullptr && n2 != nullptr)
    {
        if (n1->val < n2->val)
        {
            n->next = n1;
            n1 = n1->next;
        }
        else
        {
            n->next = n2;
            n2 = n2->next;
        }
        n = n->next;
    }
    n->next = n1 == nullptr ? n2 : n1;
    return dummy->next;
}

int main()
{
}

// go 同上

# python
from typing import Optional


def main():
    pass

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        if not l1:
            return l2
        if not l2:
            return l1
        
        n1 = l1
        n2 = l2

        if n1.val < n2.val:
            l = n1
            n1 = n1.next
        else:
            l = n2
            n2 = n2.next

        pre = l
        while n1 and n2:
            if n1.val < n2.val:
                pre.next = n1
                n1 = n1.next
            else:
                pre.next = n2
                n2 = n2.next
            pre = pre.next
        
        pre.next = n1 if n1 else n2
        return l


if __name__ == '__main__':
    main()

// rust
fn main() {
    // Create test lists
    let mut l1 = Some(Box::new(ListNode::new(1)));
    l1.as_mut().unwrap().next = Some(Box::new(ListNode::new(2)));
    l1.as_mut().unwrap().next.as_mut().unwrap().next = Some(Box::new(ListNode::new(4)));

    let mut l2 = Some(Box::new(ListNode::new(1)));
    l2.as_mut().unwrap().next = Some(Box::new(ListNode::new(3)));
    l2.as_mut().unwrap().next.as_mut().unwrap().next = Some(Box::new(ListNode::new(4)));

    // Print original lists
    print_list(&l1);
    print_list(&l2);

    // Merge lists
    let merged = merge_two_lists(l1, l2);
    print_list(&merged);
}

pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    fn new(val: i32) -> Self {
        ListNode { val, next: None }
    }
}

// Helper function to print the list
fn print_list(list: &Option<Box<ListNode>>) {
    let mut n = list;
    while let Some(node) = n {
        print!("=>{}", node.val);
        n = &node.next;
    }
    println!();
}

pub fn merge_two_lists(
    l1: Option<Box<ListNode>>,
    l2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
    let mut n1 = l1;
    let mut n2 = l2;
    if n1.is_none() {
        return n2;
    }
    if n2.is_none() {
        return n1;
    }

    let mut dummy = ListNode::new(0);
    let mut cur = &mut dummy;

    while n1.is_some() && n2.is_some() {
        if n1.as_ref().unwrap().val <= n2.as_ref().unwrap().val {
            let mut node = n1.unwrap();
            n1 = node.next.take();
            cur.next = Some(node);
        } else {
            let mut node = n2?;
            n2 = node.next.take();
            cur.next = Some(node);
        }
        cur = cur.next.as_mut().unwrap();
    }
    cur.next = n1.or(n2);
    dummy.next
}

// js

// ts
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 *      
 */

function mergeTwoLists(
  l1: ListNode | null,
  l2: ListNode | null
): ListNode | null {
  let n1 = l1;
  let n2 = l2;
  if (!n1) return n2;
  if (!n2) return n1;

  let l = new ListNode();
  if (n1.val < n2.val) {
    l = n1;
    n1 = n1.next;
  } else {
    l = n2;
    n2 = n2.next;
  }

  let n = l;
  while (n1 && n2) {
    if (n1.val < n2.val) {
      n.next = n1;
      n1 = n1.next;
    } else {
      n.next = n2;
      n2 = n2.next;
    }
    n = n.next;
  }

  n.next = n1 || n2;
  return l;
}