跳转至

链表#
发布于2021-02-02
上次编辑2021-04-20

单链表#

1
2
3
4
5
6
7
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) {}
};

1
2
3
4
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

构建链表#

  • 头插法：构建的链表的元素与输入的元素方向相反。
  • 尾插法：构建的链表的元素与输入的元素方向相同。

反转链表#

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev, cur = None, head

        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt

        return prev

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *prev = nullptr, *cur = head;

        while (cur) {
            auto next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }

        return prev;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head

        rhs = self.reverseList(head.next)

        head.next.next = head
        head.next = None

        return rhs

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;

        auto rhs = reverseList(head->next);

        head->next->next = head;
        head->next = nullptr;

        return rhs;
    }
};

例题#

返回顶部

在手机上阅读