206. 反转链表

描述

• 反转一个单链表。

进阶

• 链表可以迭代或递归地反转。你能否两个都实现一遍？

思路

1. 迭代版本：利用二个指针，每次将node的后续节点保存在tmp中，然后将node指向pre，接着pre后移，node后移。
2. 递归版本：和迭代版本的大体思路类似。其本质就是将pre=head; head=tmp; 两步变成了递归执行。

// 迭代版本
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. 合并两个有序链表

描述

• 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例

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

思路

1. 因为链表是有序的，所以谁小谁加入新的列表上。

Tips

1. 采用“指向头结点的节点”会省去很多冗余的代码，麻烦的条件判断。
2. 链表不是数组，一旦链上了就全部串接上去了。

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，链表只要链上了就全串上了，不是数组。
    if (l2 != NULL) pNode->next = l2;
    return pHead->next;
  }
};