链表easy专题

本文最后更新于：2023年1月30日 下午

总结

  1. yes代表独立做出来,no代表没有独立做出来(no越多代表越没有思路)，需要看一下解法
  2. 递归，链表的定义具有递归的性质，因此链表题目常可以用递归的方法求解。
  3. 链表的关键就是断链和重链，无论是递归还是非递归，都需要在合适的地方断链和重链
  4. 对于链表问题，如果需要对头节点可能发生变更，通常需要先初始化一个预先指针 pre，该指针的下一个节点指向真正的头结点 head。

LeetCode21 合并两个有序链表 (yes)

（1）题目：

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的

（2）思路：

  • 双指针：声明头部指针，声明index索引指针，通过比较value来确定index.next的指向
  • 递归：处理好边界跳出的时机

（3）代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
   * 双指针
   */
  public ListNode mergeTwoLists1(ListNode list1, ListNode list2) {
      if (list1 == null) {
          return list2;
      }
      if (list2 == null) {
          return list1;
      }
      ListNode head, index;
      if (list1.val > list2.val) {
          head = index = list2;
          list2 = list2.next;
      } else {
          head = index = list1;
          list1 = list1.next;
      }

      while (list2 != null && list1 != null) {
          if (list1.val > list2.val) {
              index.next = list2;
              list2 = list2.next;
          } else {
              index.next = list1;
              list1 = list1.next;
          }
          index = index.next;
      }

      if (list1 != null) {
          index.next = list1;
      }
      if (list2 != null) {
          index.next = list2;
      }

      return head;
  }


  /**
   * 递归
   */
  public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
      if (list1 == null) {
          return list2;
      } else if (list2 == null) {
          return list1;
      } else if (list1.val > list2.val) {
          list2.next = mergeTwoLists(list1, list2.next);
          return list2;
      } else {
          list1.next = mergeTwoLists(list1.next, list2);
          return list1;
      }
  }

LeetCode83 删除链表中重复元素(yes)

（1）题目：

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

（2）思路：

  • 断链和重链

（3）代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
   * 递归
   */
  public ListNode deleteDuplicates(ListNode head) {
      if (head == null || head.next == null) {
          return head;
      }

      ListNode nHead = deleteDuplicates(head.next);
      if (nHead != null && nHead.val == head.val) {
          head.next = nHead.next;
          // nHead.next = null;
      }
      return head;
  }

LeetCode141 环形链表(yes)

（1）题目：

给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。如果链表中存在环 ，则返回 true 。 否则，返回 false 。

（2）思路：

  • 快慢指针，指针能够再次相遇则代表有环

（3）代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 /**
   * 快慢指针
   */
public boolean hasCycle(ListNode head) {
      if (head == null || head.next == null) {
          return false;
      }
      ListNode quick = head;
      while (quick != null && quick.next != null) {
          quick = quick.next.next;
          head = head.next;
          if (quick == head) {
              return true;
          }
      }
      return false;
  }

LeetCode 环形链表2 (no,no)

（1）题目：

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null

（2）思路：

  • 设定head到入口节点长度为a(不包含入口), 环的长度为b，则在二者相遇时可以得到以下公式

    • quick = slow + n * b
    • quick = 2 * slow

  • 上述两个公式通过合并的方式可以得到quick和slow

    • slow = n * b
    • quick = 2 * n * b

  • 综上分析

    • 在相遇点时，slow已经走了nb长度，而quick走了2nb
    • 在quick走到到相遇点之前的入口点是走了a + nb(先走了a，在绕环走了nb，然后在走了一段达到相遇点)
    • 所以slow想到达quick走过的相遇点，则需要再走a。而此时只要一个节点index从head出发，slow和index就可以在入口处相遇

（3）代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 双指针、快慢指针
 * 设定head到入口节点长度为a(不包含入口), 环的长度为b
 */
public ListNode detectCycle(ListNode head) {
    if (head == null || head.next == null) {
        return null;
    }
    ListNode quick = head.next.next, slow = head.next;
    while (quick != null && quick.next != null && quick != slow) {
        quick = quick.next.next;
        slow = slow.next;
    }
    if (quick != slow) {
        return null;
    }
    while (slow != head) {
        slow = slow.next;
        head = head.next;
    }
    return head;
}

LeetCode160 相交链表 (no)

（1）题目：

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null

（2）思路：

  • 每次A,B同时移动，如果相同且不为空则证明存在相同节点
  • A先从自身开始遍历，到尾部在从B继续遍历
  • B先从自身开始遍历，到尾部在从A继续遍历
  • 这样AB遍历相同长度，此时在任意一个节点相同则证明是相同节点

（3）代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
        return null;
    }

    ListNode indexA = headA;
    ListNode indexB = headB;
    while (indexA != indexB) {
        indexA = indexA != null ? indexA.next : headB;
        indexB = indexB != null ? indexB.next : headA;
    }
    return indexA;
}

LeetCode203 移除链表元素 (yes)

（1）题目：

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

（2）思路：

  • 非递归，处理头部相同、中间相同、尾部相同的不同情况
  • 递归，链表的定义具有递归的性质，因此链表题目常可以用递归的方法求解。

（3）代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * 相同的value在头部
 * 相同的value在中间
 * 相同的value在尾部
 */
public ListNode removeElements1(ListNode head, int val) {
    if (head == null) {
        return null;
    }

    ListNode nHead = head, index = head;
    // 第一个元素相同
    while (head != null && head.val == val) {
        nHead = head.next;
        index = nHead;
        head = head.next;
    }
    if (head == null || head.next == null) {
        return nHead;
    }

    head = head.next;
    // 第一个元素不相同
    while (head != null) {
        if (head.val == val) {
            index.next = head.next;
            head = head.next;
        } else {
            head = head.next;
            index = index.next;
        }
    }
    return nHead;
}

public ListNode removeElements(ListNode head, int val) {
    if (head == null) {
        return null;
    }

    head.next = removeElements(head.next, val);

    return head.val == val ? head.next : head;
}

LeetCode206 反转链表(no)

（1）题目：

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

（2）思路：

  • 非递归，需要额外处理1,2,3个元素的不同情况
  • 递归，

（3）代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
   * 递归解法
   */
  public ListNode reverseList1(ListNode head) {
      if (head == null || head.next == null) {
          return head;
      }

      ListNode nHead = reverseList1(head.next);
      head.next.next = head; // 核心内容，让中间的元素变更指向
      head.next = null;
      return nHead;
  }

  /**
   * 非递归解法
   */
  public ListNode reverseList(ListNode head) {
      if (head == null || head.next == null) {
          return head;
      }

      ListNode pre = head, suf = head.next, temp;
      do {
          temp = suf.next;
          suf.next = pre;
          if (pre == head) { // 核心内容，第一个元素需要断链，而后面的不需要，因为已经通过赋值的方式断链
              pre.next = null;
          }

          pre = suf;
          suf = temp;
      } while (suf != null);

      return pre;
  }

  /**
   * 非递归解法2, 比第一种非递归更简洁
   */
public ListNode reverse(ListNode head) {
      ListNode prev = null;
      while (head != null) {
          ListNode next = head.next;
          head.next = prev;
          prev = head;
          head = next;
      }
      return prev;
  }

LeetCode234 回文链表(no)

（1）题目：

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

（2）思路：

  • 计数+栈，先计算链表的长度，在中间的问题通过入栈出栈对比元素
  • 快慢指针，通过快慢指针定位到中间为止，在反转后半段链表，比较值

（3）代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/**
   * 计数 + 栈
   */
  public boolean isPalindrome1(ListNode head) {
      if (head == null) {
          return false;
      }
      if (head.next == null) {
          return true;
      }

      int count = 0;
      ListNode index = head;
      while (index != null) {
          count++;
          index = index.next;
      }

      Deque<ListNode> stack = new ArrayDeque<>();
      index = head;
      for (int i = 0; i < count / 2; i++) {
          stack.push(index);
          index = index.next;
      }
      if (count % 2 != 0) {
          index = index.next;
      }

      while (index != null) {
          if (index.val != stack.pop().val) {
              return false;
          }
          index = index.next;
      }

      return true;
  }

  /**
   * 快慢指针
   */
  public boolean isPalindrome(ListNode head) {
      if (head == null) {
          return false;
      }
      if (head.next == null) {
          return true;
      }

      ListNode quick = head, slow = head;
      while (quick.next != null && quick.next.next != null) {
          quick = quick.next.next;
          slow = slow.next;
      }
      if (quick.next != null) {
          slow = slow.next;
      }

      ListNode reverse = reverse(slow);
      quick = head;
      while (reverse != null) {
          if (quick.val != reverse.val) {
              return false;
          }
          quick = quick.next;
          reverse = reverse.next;
      }
      return true;
  }

  /**
   * 反转链表
   */
  public ListNode reverse(ListNode head) {
      ListNode prev = null;
      while (head != null) {
          ListNode next = head.next;
          head.next = prev;
          prev = head;
          head = next;
      }
      return prev;
  }

剑指Offer06 倒序打印链表 (yes)

（1）题目：

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

（2）思路：

  • 递归更优雅的方式，不使用数组拷贝，而是建立一个arraylist，这样可以避免使用System.arraycopy从而减少遍历次数和内存

（3）代码：

1
2
3
4
5
6
7
8
9
10
11
public int[] reversePrint(ListNode head) {
    if (head == null) {
        return new int[0];
    }

    int[] ints = reversePrint(head.next);
    int[] res = new int[ints.length + 1];
    System.arraycopy(ints, 0, res, 0, ints.length);
    res[ints.length] = head.val;
    return res;
}

剑指Offer22 链表中倒数第k个节点 (yes)

（1）题目：

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

（2）思路：

  • 先让一个指针走K，然后另一个从头部出发，当第一个达到尾部则后一个出发的是倒数第K个
  • 需要处理k大于链表和等于链表的特殊情况

（3）代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public ListNode getKthFromEnd(ListNode head, int k) {
    if (head == null || k < 1) {
        return null;
    }

    ListNode index = head;
    int i = 0;
    while (i != k && index!= null) {
        index = index.next;
        i++;
    }
    if (i==k && index == null) {
        return head;
    }
    if (i != k && index == null) {
        return null;
    }

    while (index != null) {
        head = head.next;
        index = index.next;
    }

    return head;
}
刷题/Leetcode > 链表
#LeetCode #easy #链表
链表easy专题
http://coder-xieshijie.cn/2023/01/16/刷题/链表easy专题/
作者
谢世杰
发布于
2023年1月16日
更新于
2023年1月30日
许可协议