206. 反轉(zhuǎn)鏈表

描述

• 反轉(zhuǎn)一個單鏈表。

進階

• 鏈表可以迭代或遞歸地反轉(zhuǎn)。你能否兩個都實現(xiàn)一遍？

思路

1. 迭代版本：利用二個指針，每次將node的后續(xù)節(jié)點保存在tmp中，然后將node指向pre，接著pre后移，node后移。
2. 遞歸版本：和迭代版本的大體思路類似。其本質(zhì)就是將pre=head; head=tmp; 兩步變成了遞歸執(zhí)行。

// 迭代版本
class Solution_206_01 {
 public:
  ListNode* reverseList(ListNode* head) {
    if (head == NULL) return NULL;
    ListNode* pre = NULL;
    while (head) {
      ListNode* tmp = head->next;
      head->next = pre;
      pre = head;
      head = tmp;
    }
    return pre;
  }
};

class Solution_206_02 {
 public:
  ListNode* reverseList(ListNode* head) {
    if (head == NULL) return NULL;
    ListNode* pre = NULL;
    return RecurReverse(pre, head);
  }
  ListNode* RecurReverse(ListNode* pre, ListNode* node) {
    if (node) {
      ListNode* tmp = node->next;
      node->next = pre;
      return RecurReverse(node, tmp);
    }
    return pre;
  }
};

21. 合并兩個有序鏈表

描述

• 將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的。

示例

• 輸入：1->2->4, 1->3->4
• 輸出：1->1->2->3->4->4

思路

1. 因為鏈表是有序的，所以誰小誰加入新的列表上。

Tips

1. 采用“指向頭結(jié)點的節(jié)點”會省去很多冗余的代碼，麻煩的條件判斷。
2. 鏈表不是數(shù)組，一旦鏈上了就全部串接上去了。

class Solution_21 {
 public:
  ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (l1 == NULL && l2 == NULL) return NULL;
    ListNode* pHead = new ListNode(0);
    ListNode* pNode = pHead;
    while (l1 && l2) {
      if (l1->val < l2->val) {
        pNode->next = l1;
        l1 = l1->next;
      } else {
        pNode->next = l2;
        l2 = l2->next;
      }
      pNode = pNode->next;
    }
    if (l1 != NULL) pNode->next = l1; // 這里不需要用while，鏈表只要鏈上了就全串上了，不是數(shù)組。
    if (l2 != NULL) pNode->next = l2;
    return pHead->next;
  }
};