抱佛脚-刷题系列之链表

抱佛脚一时爽，一直抱佛脚一直爽！这篇文章总结常见的链表问题~
参考链接：leetcode 剑指offer

概述

  • 涉及到删除、插入等问题的一般需要添加dummyHead
  • 若对链表中的某一段进行处理，且处理后需要把这一段接回原链表：一定要用last记录被处理的那段的最后一个节点，并把它接回原链表
  • 只要有p->next，一定要保证p不为空

反转链表相关题目

完全反转链表

ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode* dummyHead = new ListNode(-1);
    ListNode* prev = dummyHead;
    ListNode* cur = head;
    while (cur) {
        ListNode* next = cur->next;
        cur->next = prev->next;
        prev->next = cur;
        cur = next;
    }
    return dummyHead->next;
}

每k个反转链表（lc25）

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (!head || k <= 1) return head;
        ListNode* dummyHead = new ListNode(-1);
        ListNode* prev = dummyHead; // k个一组的组头的前面那个
        prev->next = head;
        ListNode* cur = head; // k个一组的组头
        for (int i = 1; cur; ++i) { // i从1开始！
          if (i % k == 0) {
            prev = reverseOneGroup(prev, cur->next); 
            cur = prev->next;
          } else {
            cur = cur->next;
          }
        }
        return dummyHead->next;
    }
    ListNode* reverseOneGroup(ListNode* pre, ListNode* end) { // 反转pre->next到end（不含end）的节点；返回反转后的组尾
        ListNode* cur = pre->next->next;
        ListNode* last = pre->next;
        while (cur != end) {
          last->next = cur->next; // 注意这里！需要把这组和原链表连起来！
          cur->next = pre->next;
          pre->next = cur;
          cur = last->next;
        }
        return last;
    }
};

反转链表的第m-n个（lc92）

ListNode* reverseBetween(ListNode* head, int m, int n) {
    if (head == nullptr) return head;
    ListNode* dummyHead = new ListNode(-1);
    dummyHead->next = head;
    ListNode* cur = head;
    ListNode* prev = dummyHead;
    int i = 1;
    while (i < m) {
        prev = prev->next;
        cur = cur->next;
        ++i;
    }
    ListNode* last = cur;
    cur = cur->next;
    while (i < n) {
        ListNode* next = cur->next;
        cur->next = prev->next;
        prev->next = cur;
        cur = next;
        ++i;
    }
    last->next = cur; // 注意这里！需要把这组和原链表连起来！
    return dummyHead->next;
}

删除重复元素

重复的元素不保留（lc82）

  • 法一：从头到尾遍历：prev记录start前的那个节点；start记录最开始的重复元素；cur记录现在遍历到的元素
ListNode* deleteDuplicates(ListNode* head) { 
  if (!head || !head->next) return head;
  ListNode* dummyHead = new ListNode(-1);
  ListNode* prev = dummyHead;
  prev->next = head;
  ListNode* start = head;
  ListNode* cur = start->next;
  int cnt = 1;
  while (cur) {
    if (cur->val == start->val) {
      cur = cur->next;
      ++cnt;
    } else {
      if (cnt > 1) prev->next = cur;
      else prev = start;
      start = cur;
      cur = cur->next;
      cnt = 1;
    }
  }
  if (cnt > 1) prev->next = nullptr;
  return dummyHead->next;
}
  • 法二：递归
ListNode* deleteDuplicates(ListNode* head) {
    if (!head) return head;
    if (head->next && head->val == head->next->val) {
        while (head->next && head->val == head->next->val) {
            head = head->next;
        }
        return deleteDuplicates(head->next);
    }
    head->next = deleteDuplicates(head->next);
    return head;
}

重复的元素只保留一个（lc83）

  • 法一：遍历并删除：start记录最开始的重复元素；cur记录现在遍历到的元素
ListNode* deleteDuplicates(ListNode* head) {
  if (!head || !head->next) return head;
  ListNode *start = head, *cur = head->next;
  bool flag = false;
  while (cur) {
    if (cur->val == start->val) {
      cur = cur->next;
      flag = true;
    } else {
      start->next = cur;
      start = start->next;
      cur = start->next;
      flag = false;
    }
  }
  if (flag) start->next = nullptr;
  return head;
}
  • 法二：递归
ListNode* deleteDuplicates(ListNode* head) {
    if (!head || !head->next) return head;
    head->next = deleteDuplicates(head->next);
    return (head->val == head->next->val) ? head->next : head;
}

链表环

求环入口（jz55）

ListNode* EntryNodeOfLoop(ListNode* pHead) {
    if (!pHead || !pHead->next) return NULL;
    ListNode* fast = pHead->next->next;
    ListNode* slow = pHead->next; // 注意是head->next而不是head！
    while (slow != fast) {
        if (!fast || !fast->next) return NULL;
        fast = fast->next->next;
        slow = slow->next;
    }
    fast = pHead;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

判断是否有环（lc141）

  bool hasCycle(ListNode *head) {
    if (!head || !head->next) return false;
    ListNode* slow = head->next;
    ListNode* fast = head->next->next;
    while (fast != slow) {
      slow = slow->next;
      if (!fast || !fast->next) return false;
      fast = fast->next->next;
    }
    return true;
  }

其他题目

从中间拆分链表

void splitList(ListNode* head) { // 第一段链表长度<=第二段链表长度，即拆分点在中间偏左的位置
    if (!head || !head->next) return;
    ListNode* slow = head;
    ListNode* fast = head->next->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode* fast = slow->next; // 第二段链表从fast开始到最后
    slow->next = nullptr; // 第一段链表从head开始到slow
}

链表排序（lc148）

  • 思路：先把链表从中间断开，分别sort链表，再merge两个链表
  • 注意：merge(sortList(head), sortList(slow))

重排链表（lc143）

  • 思路：先把链表从中间断开，再反转后半段，再merge

获取倒数第k个节点

ListNode* getNthFromEnd(ListNode* head, int n) {
    if (!head) return head;
    ListNode* slow = head;
    ListNode* fast = head;
    while (n-- && fast) {
        fast = fast->next;
    }
    if (n > 0) return nullptr; // 没有n个节点
    while (fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

求两个链表的交点

  ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    if (!headA || !headB) return nullptr;
    ListNode* l1 = headA;
    ListNode* l2 = headB;
    bool flag1 = false, flag2 = false;
    while (l1 != l2) {
      if (l1 == nullptr) {
        if (flag1) return nullptr; // 第二次碰到链表结尾，说明两个链表无交点
        flag1 = true;
        l1 = headB;
      } else {
        l1 = l1->next;
      }
      if (l2 == nullptr) {
        if (flag2) return nullptr; // 第二次碰到链表结尾，说明两个链表无交点
        flag2 = true;
        l2 = headA;
      } else {
        l2 = l2->next;
      }
    }
    return l1;
  }

链表表示的两数相加（lc445）

  • 思路：用两个栈分别装两个链表各个节点的值，然后分别出栈做大数相加

回文链表（lc234）

  • 思路：找到中点，反转后半段，依次比较
bool isPalindrome(ListNode* head) {
  if (!head || !head->next) return true;
  // 找到中点并断开（前半段长度<=后半段）
  ListNode* slow = head;
  ListNode* fast = head->next->next;
  while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
  }
  ListNode* head2 = slow->next;
  slow->next = nullptr;
  // 反转后半段
  ListNode* dummyHead = new ListNode(-1);
  dummyHead->next = head2;
  ListNode* cur = head2->next;
  while (cur) {
    ListNode* nextNode = cur->next;
    cur->next = dummyHead->next;
    dummyHead->next = cur;
    cur = nextNode;
  }
  head2 = dummyHead->next;
  // 比较前半段和后半段
  while (head && head2) {
    if (head->val != head2->val) return false;
    head = head->next;
    head2 = head2->next;
  }
  return true;
}

旋转链表（lc61）

  • 法一：双指针
class Solution {
public:
    int getLength(ListNode* head) {
        int res = 0;
        while (head) {
            ++res;
            head = head->next;
        }
        return res;
    }

    ListNode* rotateRight(ListNode* head, int k) {
        if (!head || !head->next) return head;
        ListNode *fast = head, *slow = head, *prevSlow = head, *prevFast = head;
        int len = getLength(head);
        k = k % len;
        while (k--) {
            fast = fast->next;
            //if (!fast) fast = head;
        }
        if (fast == head) return head;
        while (fast) {
            prevSlow = slow;
            slow = slow->next;
            prevFast = fast;
            fast = fast->next;
        }
        prevSlow->next = nullptr;
        prevFast->next = head;
        return slow;
    }
};
  • 法二：先遍历整个链表获得链表长度n，然后此时把链表头和尾链接起来，在往后走n - k % n个节点就到达新链表的头结点前一个点，这时断开链表即可
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容