[教學] Leetcode-Merge Two Sorted Lists－一個小小工程師的心情抒發天地

我發現... 現在的業務量真的很難讓我每天一更又要維持原本的生活, 嘖嘖, 不過不得不說, 自從開始用這個方式後, 真的能夠比較快速的進入醒腦狀態... 比喝咖啡還有效; 而這一次的題目是Linklist, 話說我也好久沒有用到這個東西, 說真的自從各種像是vector, map, stack 出來後, 對於linklist的需求好像就越來越少了;

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

The number of nodes in both lists is in the range [0, 50].
-100 <= Node.val <= 100
Both list1 and list2 are sorted in non-decreasing order.

struct Node
{
int Data;
Node * pNext;
};

void InitNode(Node *head, int value) {
head->Data = value;
head->pNext = NULL;
}

void AddNewNode(Node *head, int n) {

   Node* newNode   = new Node;
   newNode->Data   = n;
   newNode->pNext   = NULL;

   Node* current = head;
   while (current)
   {
       if (current->pNext == NULL) {
           current->pNext = newNode;
           return;
       }
       current = current->pNext;
   }
}

void PrintList(Node * _list) {

   Node*temp = _list;
   while (temp != NULL)
   {
       printf("%d \n", temp->Data);
       temp = temp->pNext;
   }
}

Node* margeTwoList(Node* list1, Node* list2)
{

   // if list1 happen to be NULL
   // we will simply return list2.
   if (list1 == NULL)
       return list2;

   // if list2 happen to be NULL
   // we will simply return list1.
   if (list2 == NULL)
       return list1;

   Node *ptr = list1;
   if (list1->Data <= list2->Data)
   {
       ptr = list2;
       list2 = list2->pNext;
   }
   else
   {
       list1 = list1->pNext;
   }
   // till one of the list doesn't reaches NULL
   Node* curr = ptr;
   while (list1 && list2) {
       if (list1->Data < list2->Data) {
           curr->pNext = list1;
           list1 = list1->pNext;
       }
       else
       {
           curr->pNext = list2;
           list2 = list2->pNext;
       }
       curr = curr->pNext;
   }
   // adding remaining elements of bigger list.
   if (!list1)
       curr->pNext = list2;
   else
       curr->pNext = list1;
   return ptr;
}