java合并两个有序链表

1.题目：
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

链表1：1->3->5->7->9->11
链表2： 2->4->6->8
输出新链表：1->2->3->4->5->6->7->8->9->11
2.解题思路：
新建一个链表，来存储节点。让head1和head2进行比较，数值较小的那个存放在新的链表中。如是其中一个链表遍历完为空链表后，将另一个链表的剩余的所有节点都存进新链表当中。
3.采用迭代和递归的方式实现，看详细代码

package com.example.nqct.linkedlisttest;

import android.os.Bundle;
import android.util.Log;

import androidx.annotation.Nullable;
import androidx.appcompat.app.AppCompatActivity;

import com.example.nqct.R;

/**
 * 合并两个有序链表
 */
public class LinkedListMergeActivity extends AppCompatActivity {
    private static final String TAG = LinkedListMergeActivity.class.getName();

    @Override
    protected void onCreate(@Nullable Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);

        Node newNode = mergeNode(getNodeList1(), getNodeList2());
        //Node newNode = recursionMergeNode(getNodeList1(), getNodeList2());
        printNodeData(newNode);
    }

    public void printNodeData(Node node) {
        if (node != null) {
            Log.d(TAG, "printNodeData==>data="+node.data);
            printNodeData(node.next);
        }
    }
    
   /**
     * 合并两个链表
     * @param node1
     * @param node2
     * @return
     */
    private Node mergeNode(Node node1, Node node2) {
        //为方便遍历，分别为两个链表创建指针，用于链表移动
        Node head1 = node1;
        Node head2 = node2;
        //创建新的链表节点
        Node newNode = new Node();
        //创建新的链表节点指针
        Node newHeadNode = newNode;
        while (head1 != null && head2 != null) {
            if (head1.data <= head2.data) {
                newHeadNode.next = head1;
                head1 = head1.next;
            } else {
                newHeadNode.next = head2;
                head2 = head2.next;
            }
            newHeadNode = newHeadNode.next;
        }

        if (head1 == null) {
            newHeadNode.next = head2;
        }
        if (head2 == null) {
            newHeadNode.next = head1;
        }
        //之所以返回newNode.next，是因为初始创建的node节点值为0
        return newNode.next;
    }

   /**
     * 递归合并两个链表
     * @param node1
     * @param node2
     * @return
     */
    private Node recursionMergeNode(Node node1, Node node2) {
        if (node1 == null) {
            return node2;
        }
        if (node2 == null) {
            return node1;
        }
        Node newNode = null;
        if (node1.data <= node2.data) {
            newNode = node1;
            newNode.next = recursionMergeNode(node1.next, node2);
        } else {
            newNode = node2;
            newNode.next = recursionMergeNode(node1, newNode.next);
        }
        return newNode;
    }

    private class Node {
        public int data;
        public Node next;

        public Node() {}

        public Node(int data) {
            this.data = data;
        }
    }

    private Node getNodeList1() {
        Node head = new Node(1);
        Node node2 = new Node(3);
        Node node3 = new Node(5);
        Node node4 = new Node(7);
        Node node5 = new Node(9);
        Node node6 = new Node(11);
        head.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = null;
        return head;
    }

    private Node getNodeList2() {
        Node head = new Node(2);
        Node node2 = new Node(4);
        Node node3 = new Node(6);
        Node node4 = new Node(8);
        head.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = null;
        return head;
    }
}