408算法题leetcode--第15天

143. 重排链表

• 143. 重排链表
• 思路：之前三题的合并
• 时间：O(n)；空间：O(1)

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* findMiddle(ListNode* head){ListNode* p = head, *q = head;// q移动2步，p移动一步while(q->next && q->next->next){q = q->next->next;p = p->next;}return p;}ListNode* reverseList(ListNode* head){ListNode* pre = nullptr, *cur = head, *next = nullptr;while(cur){next = cur->next;cur->next = pre;pre = cur;cur = next;}return pre;}void mergeList(ListNode* l, ListNode* r){ListNode* p = l, *q = r;while(p && q){ListNode* t1 = p->next, *t2 = q->next;p->next = q;p = t1;q->next = p;q = t2;}}void reorderList(ListNode* head) {if(head == nullptr) return;// 思路：找到链表中点，右链表逆转，逐一合并左右链表节点// 1. 找中点ListNode* mid_head = findMiddle(head);ListNode* right_head = mid_head->next;mid_head->next = nullptr;// 2. 右边翻转right_head = reverseList(right_head);// 3. 合并两个链表mergeList(head, right_head);}
};

2. 两数相加

• 2. 两数相加
• 思路：注释
• 时间：O(max(m, n))；空间：O(1)

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {// 思路1：读取数字，倒序，相加，倒序，链表// 思路2：对应位置相加，进位到后一位ListNode* dummy_head = new ListNode();ListNode* cur = dummy_head;int carry = 0;while(l1 || l2 || carry){int a = l1 ? l1->val : 0;int b = l2 ? l2->val : 0;int sum = a + b + carry;carry = sum / 10;cur->next = new ListNode(sum % 10);cur = cur -> next;if(l1) l1 = l1->next;if(l2) l2 = l2->next;}return dummy_head->next;}
};

445. 两数相加 II

• 445. 两数相加 II
• 思路：先翻转，再相加（同上）
• 时间：O(n)；空间：O(1)

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode* head){ListNode* pre = nullptr, *cur = head, *next = nullptr;while(cur){next = cur->next;cur->next = pre;pre = cur;cur = next;}return pre;}ListNode* addList(ListNode* lhs, ListNode* rhs){ListNode* dummy_head = new ListNode();ListNode* cur = dummy_head;int carry = 0;while(carry || lhs || rhs){int a = lhs ? lhs->val : 0;int b = rhs ? rhs->val : 0;int sum = a + b + carry;carry = sum / 10;cur->next = new ListNode(sum % 10);cur = cur->next;if(lhs) lhs = lhs->next;if(rhs) rhs = rhs->next;}return dummy_head->next;}ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {// 反转2个链表，然后相加ListNode* p = reverseList(l1), *q = reverseList(l2);ListNode* ret = addList(p, q);return reverseList(ret);}
};