LinkedList-Medium

2020-04-25
Abstract：leetcode 链表中等难度题合集

2. Add Two Numbers

image-20200425175926684

解法一

链表模拟加减法，先计算长度相等的部分，如果有一条链更长，那么第一次while结束后继续检查进位，不过这样子写很不优雅，下面优化版改了一下

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int carry = 0;
        ListNode* ans = new ListNode(-1);
        ListNode* curr = ans;
        while(l1 && l2){
            curr->next = new ListNode(l1->val + l2->val + carry);
            curr = curr->next;
            if(curr->val > 9) {
                curr->val -= 10;
                carry = 1;
            }
            else carry = 0;
            l1 = l1->next;
            l2 = l2->next;
        }
        curr->next = l1 == NULL ? l2 : l1;
        while(carry == 1 && curr->next){
            curr = curr->next;
            curr->val += 1;
            if(curr->val > 9) curr->val -= 10;
            else carry = 0;
        }
        if(curr->next == NULL && carry == 1) curr->next = new ListNode(1); 
        return ans->next;
    }
};

优化版

没必要剪断之类的，如果某条链为0，直接加零就完事了

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int carry = 0;
        ListNode* head = new ListNode(-1);
        ListNode* curr = head, * p1 = l1, * p2 = l2;
        while(p1 != NULL || p2 != NULL){
            int n1 = p1 == NULL ? 0 : p1->val;
            int n2 = p2 == NULL ? 0 : p2->val;
            int val = n1 + n2 + carry;
            if(val > 9){
                val -= 10;
                carry = 1;
            }
            else carry = 0;
            curr->next = new ListNode(val);
            curr = curr->next;
            if(p1 != NULL) p1 = p1->next;
            if(p2 != NULL) p2 = p2->next;
        }
        if(carry == 1) curr->next = new ListNode(1);
        return head->next;
    }
};

19. Remove Nth Node From End of List

image-20200429150847161

解法一：快慢指针

  • 经典链表操作快慢操作，类似的还有取中值

  • 由于n是合法的，不需要考虑超出长度的问题

class Solution {
public:
	ListNode* removeNthFromEnd(ListNode* head, int n) {
		ListNode* h = new ListNode(-1);
		h->next = head;
		ListNode* fast = h, * slow = h;
		for (int i = 0; i <= n; i++)
			fast = fast->next;
		for (fast; fast != NULL; fast = fast->next, slow = slow->next);
		slow->next = slow->next->next;
		return h->next;
	}
};

86. Partition List

image-20200502140417451

解法一：一次遍历

加个表头方便操作

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if(head == NULL) return head;
        ListNode* curr = head, * n1 = new ListNode(-1), * n2 = new ListNode(-1),
        * curr_1 = n1, * curr_2 = n2;
        for(curr; curr != NULL; curr = curr->next){
            if(curr->val >= x){
                curr_2->next = new ListNode(curr->val);
                curr_2 = curr_2->next;
            }
            else{
                curr_1->next = new ListNode(curr->val);
                curr_1 = curr_1->next;
            }
        }
        curr_1->next = n2->next;
        return n1->next;
    }
};

82. Remove Duplicates from Sorted List II

image-20200502142031537

解法一：

因为单链表不能回溯且要求删掉所有出现重复的元素，因此需要进行预判，也就是

curr->next->next->val == curr->next->val

另外删完一组数后不要急着令curr = curr->next，因为可能存在连续的重复元素，如果直接指向下一个，那“预判”就失效了，因此我们让curr->next = n，这样就能用while继续预判了

再另外，首位也可能重复，所以开一个新表头来预判首位元素

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* prev = new ListNode(-1), * curr = prev;
        prev->next = head;
        for (curr; curr != NULL; curr = curr->next){
            while (curr->next && curr->next->next && curr->next->next->val == curr->next->val) {
                int val = curr->next->val;
                ListNode* n = curr->next;
                for (n; n != NULL && n->val == val; n = n->next);
                curr->next = n;
            }
        }
        return prev->next;
    }
};

92. Reverse Linked List II

image-20200502153133977

解法一：利用reverse

已经写过reverse的代码了，怎么复用结果来解决这道题呢？很简单，掐掉头和尾，把中间的反转，再拼起来就行了

  • 原版的reverse略有改动，prev 为反转后的尾部，原本反转后的尾部为NULL，现在为了方便我们改成“掐得的tail”
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode* dummy = new ListNode(-1), * prev = dummy;
        dummy->next = head;
        for(int i = 1; i < m; i++) prev = prev->next;
        ListNode* curr = prev->next;
        for(int i = m; i < n; i++) curr = curr->next;
        ListNode* tail = curr->next;
        curr->next = NULL;
        prev->next = reverse(prev->next, tail);
        return dummy->next;
    }

    ListNode* reverse(ListNode* head, ListNode* prev){
        ListNode* curr = head;
        while(curr != NULL){
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

142. Linked List Cycle II

image-20200510154722042

解法一：快慢指针

不同于检测环，会想当然地以为快慢指针相等时即为结果，但是一轮找出的结果并不一定是环的入口

因此要从head和交点开始重新一轮遍历，当两者相遇时，即为环的入口

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(!head) return NULL;
        ListNode* cycle = getCycle(head);
        if(!cycle) return NULL;
        ListNode* curr = head;
        while(curr != cycle) {
            curr = curr->next;
            cycle = cycle->next;
        }
        return cycle;
    }

    ListNode* getCycle(ListNode* head) {
        ListNode* slow = head, * fast = head;
        while(fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast) return slow;
        }
        return NULL;
    } 
};

解法二：哈希法

比较简单的做法，要消耗O(n)空间

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode*> set;
        for(ListNode* curr = head; curr; curr = curr->next) {
            if(set.find(curr) != set.end()) return curr;
            set.insert(curr);
        } 
        return NULL;
    } 
};

61. Rotate List

image-20200516005205333

解法一：反转

  • 先计算长度，把 k 模到长度范围内
  • 将整个链表反转
  • 找到第k个节点，截断，分别反转前后两部分
  • 再拼接，即为结果
class Solution {
public:
    int getLength(ListNode* head) {
        int len = 0;
        while (head) {
            head = head->next;
            len++;
        }
        return len;
    }

    ListNode* rotateRight(ListNode* head, int k) {
        if(head == NULL) return NULL;
        int len = getLength(head);
        k = k % (len);
        ListNode* dummy = new ListNode(-1);
        dummy->next = reverse(head, NULL);
        
        ListNode* curr = dummy;
        for(int i = 0; i < k; i++) curr = curr->next;
        ListNode* next = curr->next;
        curr->next = NULL;
        return reverse(dummy->next, reverse(next, NULL));
    }

    ListNode* reverse(ListNode* head, ListNode* tail) {
        ListNode* prev = tail;
        ListNode* curr = head;
        while(curr != NULL) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};
© 2020 Overyam - Powered by Hexo - Theme Chan