当前位置:   article > 正文

【刷题笔记】链表篇2

【刷题笔记】链表篇2

这两天又刷了几道链表的题,在此做个记录。

82. 删除排序链表中的重复元素 II

这道题的思路非常的暴力,就是从链表头部往后遍历,如果遇到两个节点的值一样,就把这两个节点同时去除掉,然后把这个节点的值记录一下,继续往后遍历,如果有和这个值相等的节点,继续去除。

有同学问了,为什么要这样做?

其实你每个节点的值都用一个变量记录一下,往后遍历的时候只要跟这个值相等就删除,不等的话就更新这个值,不也可以吗?

是的,这样做确实可以。但是,一个根本原因就是:“只有两个节点的值先相等了,才有三个节点的值和他们相等的机会”,所以我们可以只统计有两个节点的值相等的,并不需要频繁去更新这个变量。

注意:还是同大多数链表的题目一样,只要涉及删除头节点的题型,都需要在头节点前面加一个虚拟头节点。

  1. public ListNode deleteDuplicates(ListNode head) {
  2. if (head == null || head.next == null) {
  3. return head;
  4. }
  5. ListNode dumyHead = new ListNode(-1, head);
  6. ListNode cur = dumyHead;
  7. int x = -101;
  8. while (cur.next.next != null) {
  9. ListNode l1 = cur.next;
  10. ListNode l2 = cur.next.next;
  11. if (l1.val == l2.val) {
  12. x = l1.val;
  13. cur.next = l2.next;
  14. while (cur.next != null && cur.next.val == x) {
  15. cur.next = cur.next.next;
  16. }
  17. } else {
  18. cur = cur.next;
  19. }
  20. if(cur == null || cur.next == null) {
  21. break;
  22. }
  23. }
  24. return dumyHead.next;
  25. }

61. 旋转链表

这道题也非常有意思,虽然是一道中等题,但是并不难想。做法就是,先找到 k 的所指代位置的前一个节点,至于怎么找,有如下两种方法:

(1)快慢指针,就是让快指针先走k,然后再让快慢指针同时走,直到快指针走到最后。

这个方法是 19. 删除链表的倒数第 N 个结点 这道题的解法。

(2)直接遍历完链表,记录一下一共有多少个节点,然后再重新从头节点走n-k步,就找到了。

找到这个节点后,首先让原链表的尾节点的next指向头节点,形成一个环。然后在找的那个节点断开,这个题就解决了。

  1. public ListNode rotateRight(ListNode head, int k) {
  2. if (head == null || head.next == null || k == 0) {
  3. return head;
  4. }
  5. int n = 1;
  6. ListNode cur = head;
  7. while (cur.next != null) {
  8. cur = cur.next;
  9. n++;
  10. }
  11. cur.next = head;
  12. int index = n - k % n;
  13. if (index == 0) {
  14. return head;
  15. }
  16. while (index-- > 0) {
  17. cur = cur.next;
  18. }
  19. ListNode node = cur.next;
  20. cur.next = null;
  21. return node;
  22. }

142. 环形链表 II

这道题,只要想到用map或者set结构就很容易解了。答案给的方法一是用了一个set结构,每向后遍历前都把当前节点存到set里,如果后续第一次(注意是第一次)发现了set中包含了这个节点,就说明环存在,且这个节点是入环的第一个节点。这个也很好理解,进入环的第一个节点,当走第二圈的时候也当然是最先入环。

我当时第一遍做的时候,方法与这个类似。我先想到的是第一个节点也有可能是入环的第一个节点,所以加了一个虚拟头节点(当然,如果你用上面的方法其实并不需要加这个虚拟头节点)。我是这么想的,只要是入环的第一个节点,必定有两个前面的节点的next是它。

所以,用map记录,只要有前一个节点指向它,就给它的value+1,当出现2的时候,这个节点就是我们要找的。

注意:这么做一定要把虚拟头节点加上,因为有可能第一个节点就入环了。

  1. public ListNode detectCycle(ListNode head) {
  2. Map<ListNode, Integer> map = new HashMap<>();
  3. ListNode dumyHead = new ListNode(-1, head);
  4. ListNode cur = dumyHead;
  5. map.put(cur, 0);
  6. while(cur.next != null) {
  7. cur = cur.next;
  8. map.put(cur, map.getOrDefault(cur, 0) + 1);
  9. if (map.get(cur) == 2) {
  10. return cur;
  11. }
  12. }
  13. return null;
  14. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/在线问答5/article/detail/875619
推荐阅读
相关标签
  

闽ICP备14008679号