两数相加

考虑创建哑节点dummy，使用dummy->next表示真正的头节点，避免空边界. 时间复杂度 $O\left(n\right)$O(n)

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* first = new ListNode(0);  // 哑结点
        ListNode* last = first;
        int carry = 0;
        while(l1 or l2 or carry){
            // 相加
            int bitsum = 0;
            if(l1){
                bitsum += l1->val;
                l1 = l1->next;
            }
            if(l2){
                bitsum += l2->val;
                l2 = l2->next;
            }
            if(carry){
                bitsum += carry;
            }
            // 结果
            int digit = bitsum % 10;
            carry = bitsum / 10;
            // 链表存储
            ListNode* node = new ListNode(digit);
            last->next = node;
            last = node;
        }
        last = first->next;
        delete first;
        return last;
    }
};

反转链表输出

struct ListNode {
      int val;
      struct ListNode *next;
      ListNode(int x) : val(x), next(NULL) {}
};

方法一：使用std::reverse()反转链表的输出vector

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
	    std::vector<int> ret;
        while(head!=nullptr){
            ret.push_back(head->val);
            head= head->next;
        }
        //再开辟内存，逆序遍历
        //for(auto iter=arr.rbegin(); iter<arr.rend();iter++){
        // ret.push_back(*iter);
        //}
        std::reverse(ret.begin(), ret.end());
        return ret;
    }
};

方法二：直接反转链表，改变指针指向，见下。

反转链表

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        ListNode* newHead  = nullptr;  // 必须设置为空指针
        ListNode* node;  // 临时保存删除的结点，也是新插入的结点
        while(head){
            node = head;            // 保存删除
            head = head->next;      // 更新头
            node->next = newHead;   // 重新插入
            newHead = node;         // 更新头
        }
        return newHead;
    }
};

合并两个有序链表

可以改变原有链表结构，不需要额外申请空间。

ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        ListNode* head = new ListNode(0);  // 哑结点
        ListNode* p = head;  // 遍历指针

        while(pHead1 && pHead2){
            if(pHead1->val < pHead2->val){
                p->next = pHead1;
                pHead1 = pHead1->next;
            }
            else{
                p->next = pHead2;
                pHead2 = pHead2->next;
            }
            p = p->next;
        }
        
        p->next = pHead1 ? pHead1 : pHead2;
        
        return head->next;
    }