练习题 - Zip Two Lists - 《C#》

要求：两个非空单项链表，需要将两者合并成一个且序列为顺序序列。 :::danger 不允许重新创建一个链表，将两者合并。 :::

using System;
class Node
{
    public int val;
    public Node next;
}
class Program
{
    static void Main(string[] args)
    {
        var list1 = MakeList(1,3,5,7,9,9,11,13);
        var list2 = MakeList(2,4,6,8,10,12,14);
        PrintList(list1);
        PrintList(list2);
    }
    static Node MakeList(params int[] a)
    {
        Node head = null;
        for(int  i =a.Length-1;i>=0;i--)
        {
            head = new Node { val = a[i], next = head };
        }
        return head;
    }
    static  void PrintList(Node List)
    {
        while(List != null)
        {
            Console.Write($"{List.val}->");
            List = List.next;
        }
        Console.WriteLine("null");
    }
}

using System;
namespace text
{
    class Node
    {
        public int val;
        public Node next;
    }
    class Program
    {
        static void Main(string[] args)
        {
            var list1 = MakeList(1, 3, 5, 7, 9, 9, 11, 13);
            var list2 = MakeList(2, 4, 6, 8, 10, 12, 14);
            var result = Zip(list1, list2);           
            PrintList(result);
        }
        static Node Zip(Node p, Node q)
        {
        // 此句的写法称为 “dummyhead”
        // 链表设置虚拟头结点dummyhead，这样对链表来说，
        // 第一个元素就是dummyhead的next所对应的节点元素，而不是dummyhead所对应的节点元素。
        Node head = new Node(), zipper = head;
            while (true)
            {
                if (p == null)
                {
                    zipper.next = q;
                    break;
                }
                if (q == null)
                {
                    zipper.next = p;
                    break;
                }
                if (p.val <= q.val)
                {
                    zipper.next = p;
                    p = p.next;
                }
                else
                {
                    zipper.next = q;
                    q = q.next;
                }
                zipper = zipper.next;
            }
            return head.next;
        }
        // 将数据输入链表
        // params：可以指定采用可变数量参数的方法参数。参数类型必须是一维数组。
        static Node MakeList(params int[] a)
        {
            // 头指指针为空
            Node head = null;
            for (int i = a.Length - 1; i >= 0; i--)
            {
                head = new Node { val = a[i], next = head };
            }
            return head;
        }
        // 按位输出链表元素,输出完整链表之后输出Null说明输出结束。
        static void PrintList(Node List)
        {
            while (List != null)
            {
                Console.Write("{0}->",List.val);
                List = List.next;
            }
            Console.WriteLine("null");
        }
    }
}

static Node Zip(Node p, Node q)
        {
            Node head = new Node(), zipper = head;
            while (p != null && q != null)
            {
                if (p.val <= q.val)
                {
                    zipper.next = p;
                    p = p.next;
                }
                else
                {
                    zipper.next = q;
                    q = q.next;
                }
                zipper = zipper.next;
            }
            zipper.next = p == null ? q :p ;
            // zipper.next = p ?? q;
            return head.next;

using System;
namespace text
{
    class Node
    {
        public int val;
        public Node next;
    }
    class Program
    {
        static void Main(string[] args)
        {
            var list1 = MakeList(9, 3, 5, 7, 9, 9, 11, 13);
            var list2 = MakeList(2, 4, 5, 8, 10, 12, 4);
            list1 = SortList(list1);
            list2 = SortList(list2);
            var result = Zip(list1, list2);           
            PrintList(result);
        }
        //对两个链表进行排序合并
        static Node Zip(Node p, Node q)
        {
        // 此句的写法称为 “dummyhead”
        // 链表设置虚拟头结点dummyhead，这样对链表来说，
        // 第一个元素就是dummyhead的next所对应的节点元素，而不是dummyhead所对应的节点元素。
        Node head = new Node(), zipper = head;
            while (true)
            {
                // 由于是while（ture）无线循环，故进两次判断防止链表为空，中断循环。
                if (p == null)
                {
                    zipper.next = q;
                    break;
                }
                if (q == null)
                {
                    zipper.next = p;
                    break;
                }
                if (p.val <= q.val)
                {
                    zipper.next = p;
                    p = p.next;
                }
                else
                {
                    zipper.next = q;
                    q = q.next;
                }
                zipper = zipper.next;
            }
            return head.next;
        }
        // 将数据输入链表
        // params：可以指定采用可变数量参数的方法参数。参数类型必须是一维数组。
        static Node MakeList(params int[] a)
        {
            // 头指指针为空
            Node head = null;
            for (int i = a.Length - 1; i >= 0; i--)
            {
                head = new Node { val = a[i], next = head };
            }
            return head;
        }
        // 按位输出链表元素,输出完整链表之后输出Null说明输出结束。
        static void PrintList(Node List)
        {
            while (List != null)
            {
                Console.Write("{0}->",List.val);
                List = List.next;
            }
            Console.WriteLine("null");
        }
        //从小到大排序 暴力排序，每次只排序一个节点
        static Node SortList(Node list)
        {
            bool isLoop = true;
            Node startNode = list, preNode = null;//头节点  上一个节点
            while (isLoop)
            {
                isLoop = false;
                preNode = null;
                while (startNode != null && startNode.next != null)
                {
                    Node nextNode = startNode.next;
                    if (startNode.val > nextNode.val)
                    {
                        Node temp = nextNode.next;
                        nextNode.next = startNode;
                        startNode.next = temp;
                        isLoop = true;
                        if (preNode != null)
                        {
                            preNode.next = nextNode;
                        }                            
                        else
                        {
                            list = nextNode;
                        }                            
                        startNode = list; //确保l始终都是头节点
                        break;
                    }
                    preNode = startNode;
                    startNode = nextNode;
                }
            }
            return list;
        }
    }
}

:::danger 防止输入的链表非按顺序排序，对输入的链表先进行排序在进行后续操作。 :::