206/92-反转链表

LeetCode

发布日期: 2021-09-15

LeetCode 206. Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

method 1: 迭代

ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode *pre = nullptr;
    while (head) {
        ListNode *tmp = head->next;
        head->next = pre;
        pre = head;
        head = tmp;
    }
    return pre;
}

method 2: 递归

注意：node一直指向最后一个节点

ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode *node = reverseList(head->next);
    head->next->next = head;    // 下一个节点指向自己
    head->next = nullptr;       // 自己指针置空
    return node;
}

!head是为了处理空节点[]的情况
!head->next是为了最后一个就可以返回了

LeetCode 92. Reverse Linked List II

LeetCode-92

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

method 1: 迭代

注意：--left之后left就变了，所以提前记录len

把局部反转写成子函数

// 局部反转 [head, tail)
ListNode* reverse(ListNode *head, ListNode* tail) {
    ListNode *pre = tail;
    while (head != tail) {
        ListNode *tmp = head->next;
        head->next = pre;
        pre = head;
        head = tmp;
    }
    return pre; // 返回新的头结点
}
ListNode* reverseBetween(ListNode* head, int left, int right) {
    ListNode *dummy = new ListNode(0, head);
    int len = right - left + 1;     // 先记录长度
    ListNode *start = dummy;
    while (--left) start = start->next; // left的前一个，因为要做连接
    ListNode *end = start->next;
    while (len--) end = end->next;  // 指向right的后一个
    start->next = reverse(start->next, end);    // 注意连接
    return dummy->next;
}

注意这里的start->next = reverse()，反转之后返回的是新的头结点，所以要再连接上，容易忘记

method 2: 递归

递归参数：节点、left、right、深度

递归结束条件：遇到right就返回

递归逻辑：

先去处理下一个节点

如果大于等于left，反转，下一个节点指向自己，自己指针置空

如果等于left-1，做连接

ListNode *tmp = nullptr;    // 记录right的下一个节点
ListNode* traversal(ListNode *head, int left, int right, int depth) {
    if (depth >= right) {
        tmp = head->next;
        return head;
    }
    ListNode *node = traversal(head->next, left, right, depth + 1);
    if (depth >= left) {
        head->next->next = head;
        head->next = nullptr;
    }
    else if (depth == left - 1) {
        head->next->next = tmp; // 连到right的下一个节点
        head->next = node;      // 连到right
    }
    return node;
}
ListNode* reverseBetween(ListNode* head, int left, int right) {
    ListNode *dummy = new ListNode(0, head);    // 头结点
    traversal(dummy, left, right, 0);
    return dummy->next;
}