LinkedList

链表总结

struct ListNode{
    int value;
    ListNode* next;
    ListNode(int v) : value(v), next(nullptr) { }
};

常见题型

给定链表，删除所有重复元素，使得每一个元素只出现一次

class Solution{
public:
    ListNode *deleteDuplicates(ListNode *root) {
        if (!root) return root;
        ListNode dummy(0);
        ListNode *pre = &dummy, pre->next = root;
        while (root) {
            while(root && root->value == pre->next->value)
                root = root->next;
            pre->next->next = root;
            pre = pre->next;
        }
        return dummy.next;
    }
};

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode *cur = head;
        while (cur && cur->next) {
            if (cur->value == cur->next->value)
                cur->next = cur->next->next;
            else
                cur = cur->next;
        }
        return head;
    }
};

给定链表，删除所有的重复元素

• 树是递归定义的，因此可以用递归求解

class Solution{
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head) return head;
        if (head->next && head->value == head->next->value) {
            while (head && head->next && head->value == head->next->value) {
                head = head->next;
            }
            return deleteDuplicates(head->next);
        }
        head->next = deleteDuplicates(head->next);
        return head;
    };
};

翻转链表

• 非递归

  class Solution {
  public:
      ListNode *reverseList(ListNode *head) {
          ListNode *cur = nullptr;
          while (head) {
              ListNode *next = head->next;
              head->next = cur;
              cur = head;
              head = next;
          }
          return cur;
      }
  };

• 递归

  class Solution {
  public:
      ListNode *reverseList(ListNode *head){
          if (!head || !head->next)
              return head;
          ListNode *node = reverseList(head->next);
          head->next->next = head;
          head->next = nullptr;
          return node;
      }
  };

Merge Two Lists

class Solution {
public:
    ListNode *mergeTwoList(ListNode *l1, ListNode *l2) {
        if (!l1) return l2;
        if (!l2) return l1;

        ListNode *cur = nullptr;
        if (l1->val < l2->val) {
            cur = l1;
            cur->next = mergeTwoLists(cur->next, l2);
        } else {
            cur = l2;
            cur->next = mergeTwoLists(l1, cur->next);
        }
        return cur;
    }
};