Leetcode:merge_two_sorted_lists

Leetcode:merge_two_sorted_lists

一、 題目

合並兩個排好序的鏈表，按照節點的大小排列。

二、 分析

思路很明確，可以分為下面的步驟:

1. 如果其中一個為NULL，則返回另外一個鏈表即可

2. 判斷兩個鏈表節點的大小，選取小的接入目標鏈表，並同時把鏈表後移

3. 當至少有一個鏈表為NULL時，則判斷是哪一個為空，並將另一個鏈表接入目標鏈表即可

注意:過程中由於初始時將目標鏈表置NULL，導致WA了好多次，這裡我最後返回的是next

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
    	ListNode *Listtar,*head;
    	//Listtar=NULL;
    	head=Listtar;
    	if(l1==NULL)
    	   return l2;
    	if(l2==NULL)
    	   return l1; 
		     
    	while(l1&&l2){
    		if(l1->val>l2->val){
    			Listtar->next=l2;
    			l2=l2->next;
    			Listtar=Listtar->next;
    		}
    		else {
    			Listtar->next=l1;
    			l1=l1->next;
    			Listtar=Listtar->next;
    		}
    	}
        if(l1)
        	Listtar->next=l1;
        else
        	Listtar->next=l2;
        	
        return head->next;
    }
};