合并两个有序链表——递归实现和非递归实现

待我称王封你为后i 2022-08-07 11:55 182阅读 0赞

先看代码的实现：

#include<stdio.h>
    #include<stdlib.h>
    //链表存储结构
    typedef struct Node
    {
    	int number;
    	struct Node * next;
    }Node;
    typedef struct Node * LinkList;
    
    void createListHead(LinkList * pHead, int option) //形参pHead为指向指针的指针 
    {
    	LinkList p, r;
    	int i;
    	*pHead = (LinkList)malloc(sizeof(Node));   //头结点，不存数据 
    	r = *pHead;
    	if (option == 1)  //生成奇数递增链表
    	{
    		for (i = 1; i < 11; i += 2)
    	    {
    			p = (LinkList)malloc(sizeof(Node));
    			p->number = i;
    			r->next = p;
    			r = p;
    	    }	
    	} 
    	else if (option == 2)   //生成偶数递增链表 
    	{
    		for (i = 2; i < 10; i += 2)
    	    {
    			p = (LinkList)malloc(sizeof(Node));
    			p->number = i;
    			r->next = p;
    			r = p;
    	    }		
    	} 
    
    	r->next = NULL;
    }    
    
    void displayElem(LinkList pHead)
    {
    	while (pHead)
    	{
    		printf("%d\t", pHead->number);
    		pHead = pHead->next;	
    	}
    	printf("\n");
    }
    
    LinkList mergedList(LinkList pHead1, LinkList pHead2)
    {
    	LinkList pHead = NULL;
    	if (pHead1 == NULL)
    	{
    		return pHead2;	
    	}
    	else if (pHead2 == NULL)
    	{
    		return pHead1;	
    	}
    	
    	if (pHead1->number < pHead2->number)
    	{
    		pHead = pHead1;
    		pHead->next = mergedList(pHead1->next, pHead2);	
    	}
    	else
    	{
    		pHead = pHead2;
    		pHead->next = mergedList(pHead1, pHead2->next);	
    	}
    	return pHead;
    	
    }
    int main()
    {
    	LinkList pHead1 = NULL;
    	LinkList pHead2 = NULL;
    	LinkList pHead = NULL;
    	createListHead(&pHead1, 1);   /*传入指针本身的地址，这里读者得好好想想，为什么这样 
    	                               *相当于是传入pHead1这个指针本身的地址，然后在
    								   *createListHead函数中操纵这个指针pHead1,让它有指向
    								   */ 
    	createListHead(&pHead2, 2); 
    	displayElem(pHead1->next);
    	displayElem(pHead2->next);    //pHead1和pHead2就是两个排好序的链表 
    	
    	//下面要将这两个排好序的链表组合成一个有序的递增链表 
    	pHead = mergedList(pHead1->next, pHead2->next);
    	displayElem(pHead);
    	return 0;
    }

程序运行显示结果：

![Center][]

两个有序递增的链表pHead1和pHead2,如果pHead1的第一个结点的值大于pHead2的第一个结点的值，就将pHead1的头结点赋值给pHead。然后进行下一次的比较，反之就是pHead2赋给pHead。如图：

![Center 1][]  
   这就是一个递归的过程，当到链表的最后一个结点的位置后，递归结束，依次返回各个递归函数的结点，最后组合成一个链表——合并之后的有序链表。

关于链表的知识，亲可以去查看《大话数据结构》哦！

后边在一个公司面试Java职位的时候，当时让我手写这个算法，用的是非递归的方式，看Java代码：

public class MergeSortedLinkedList {
        public class Node {
            private int number;
            private Node next;
            Node(int number, Node next) {
                this.number = number;
                this.next = next;
            }
        }
    
        /**
         * 返回头节点
         * @param isOdd
         * @return
         */
        public Node createSortedLinkedList(boolean isOdd) {
            Node p, head;
            // 头结点
            p = head = new Node(0, null);
            if (isOdd) {
                // 创建奇数有序链表
                for (int i = 1; i < 20; i += 2) {
                    Node node = new Node(i, null);
                    p.next = node;
                    p = node;
                }
            } else {
                // 创建偶数有序链表
                for (int i = 2; i < 20; i += 2) {
                    Node node = new Node(i, null);
                    p.next = node;
                    p = node;
                }
            }
            return head;
        }
    
        public Node mergeTwoSortedLinkedList(Node head1, Node head2) {
            // 注意参数判断，这个面试官也很看重 
            if (null == head1) {
                return head2;
            }
            if (null == head2) {
                return head1;
            }
    
            // 给新merge的头结点设值
            Node p, head;
            if (head1.number < head2.number) {
                head = head1;
                head1 = head1.next;
            } else {
                head = head2;
                head2 = head2.next;
            }
            p = head;
    
            while (null != head1 && null != head2) {
                if (head1.number < head2.number) {
                    p.next = head1;
                    // p指针向下移动到新结点
                    p = head1;
                    head1 = head1.next;
                } else {
                    p.next = head2;
                    p = head2;
                    head2 = head2.next;
                }
            }
            // 对剩余结点的处理 
            if (null != head1) {
                p.next = head1;
            }
            if (null != head2) {
                p.next = head2;
            }
            return head;
        }
    
        public void display(Node node) {
            while (null != node) {
                System.out.print(node.number + " ");
                node = node.next;
            }
            System.out.println();
        }
    
        public static void main(String[] args) {
            MergeSortedLinkedList sortedLinkedList = new MergeSortedLinkedList();
            Node head1 = sortedLinkedList.createSortedLinkedList(true);
            Node head2 = sortedLinkedList.createSortedLinkedList(false);
            System.out.print("Linked list one: ");
            sortedLinkedList.display(head1.next);
            System.out.print("Linked list two: ");
            sortedLinkedList.display(head2.next);
            System.out.print("Merged linked List: ");
            sortedLinkedList.display(sortedLinkedList.mergeTwoSortedLinkedList(head1.next, head2.next));
        }
    }

[Center]: /images/20220805/95641c5bfde547768370d5d6ec4d42be.png
[Center 1]: /images/20220805/500cdc21073c408f8b870db677948438.png