链表刷题集

概要

这个主要记录下刷的一些题。

链表已经看过了，之前写了篇链表的文章，这一篇，写点跟链表有关的题。主要是leetcode上的。目的是熟悉下代码，代码这东西，还是得多练。

反转链表

代码Python

题目如上图，看下我用python写的答案，代码如下：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur, pre = head, None
        while cur:
            Temp = cur.next
            cur.next = pre
            pre = cur
            cur = Temp
        return pre

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

代码C++

看完了python版本，看下C++版本，代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = head;
        ListNode* pre = nullptr;
        while(cur) {
            ListNode* Temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = Temp;
        }
        return pre;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

环形链表

题目如下图：

其实，这道题最开是我也没想明白怎么搞，后来知道了快慢指针。才知道了，接下来看看代码。

代码Python

先看下Python版本，代码如下：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        fast = slow = head
        while fast:
            if fast.next:
                fast = fast.next.next
            else:
                break
            slow = slow.next
            if fast == slow:
                return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

这是实现，只要第二个比第一个快，如果有环，总会相遇；如果没有，总会退出的。

代码Java

这次不看C++了，来看下java的版本吧。代码如下：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode fast = head.next, slow = head;
        while(slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }

        return true;
    }
}
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

小结

关于刷题

刷题这块，关于链表的，还有很多，写几道之前练过的。当然，还有很多，链表很简单，没有那么难，就是要多练习，多思考，拿出来画画，练的多了，就会了。可以去leetcode上建立一个链表刷题集，见一个，记录一个，勤练习。相信会好的。