最近做了几道翻转链表的题,写个博客汇总一下,翻转链表的各种方法。

1. 翻转完整链表

1.1. 递归

核心思想就是递归嘛,把翻转全部单链表分解成翻转head->next到末尾的全部节点,然后再把head接到翻转区域的后面。

比较关键的是注释那一行,翻转进行完成后,head->next其实就是翻转区域的最后一个元素,把head接在后面直接head->next->next = head就行了。

struct ListNode* reverse(struct ListNode* head) {
    if (head->next == NULL) return head;
    struct ListNode* last = reverse(head->next);
    head->next->next = head;  // 此时head->next是翻转区域的最后一个元素
    head->next = NULL;
    return last;
}

1.2. 非递归之头删头插

新建一个res指针,把head链表头删下来一个元素,头插在res链表里

struct ListNode* reverseList_non1(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }

    struct ListNode* cur = head;
    struct ListNode* ptr;
    struct ListNode* res = NULL;

    while (cur) {
        ptr = cur;
        cur = cur->next;

        ptr->next = res;
        res = ptr;
    }

    return res;
}

1.3. 非递归之指针指向翻转

翻转整个链表,就把每个节点间的指向都翻转一次,最后就得到了翻转的链表。

注意这种方法必须用到三个指针

struct ListNode* reverseList_non2(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }

    struct ListNode *p1, *p2, *p3;
    p1 = NULL;
    p2 = head;

    while (p2 != NULL) {
        p3 = p2->next;
        p2->next = p1;

        // 指针后移
        p1 = p2;
        p2 = p3;
    }

    return p1;
}

2. 翻转链表中第m个节点到第n个节点

2.1. 非递归

struct ListNode* reverseBetween1(struct ListNode* head, int m, int n) {
    if (head == NULL || head->next == NULL) {
        return head;
    }

    struct ListNode *start = NULL, *end = NULL;  // start指向m前一个元素 end指向n后一个元素,方便拼接
    struct ListNode *dummyHead = 
        (struct ListNode *)malloc(sizeof(struct ListNode));
    dummyHead->next = head;
    dummyHead->val = 0;
    struct ListNode *ptr = dummyHead;
    struct ListNode *res = NULL, *curr = NULL;  // 用于翻转元素
    int count = 0;

    while (count + 1 != m) {  // ptr先找到m前一个元素
        ptr = ptr->next;
        count++;
    }

    start = ptr;
    ptr = ptr->next;  
    count++;

    while (count <= n) {  // 翻转m到n之间的元素
        curr = ptr;
        ptr = ptr->next;
        count++;

        curr->next = res;
        res = curr;
    }

    end = ptr;
    start->next->next = end;
    start->next = res;

    return dummyHead->next;
}

2.2. 递归

首先写一个翻转单链表前n个节点的程序:

struct ListNode* successor = NULL;
struct ListNode* reverseN(struct ListNode* head, int n) {
    if (n == 1) {
        successor = head->next;  // successor记录原链表第n个节点的next
        return head;
    }
    struct ListNode* last = reverseN(head->next, n - 1);
    head->next->next = head;
    head->next = successor;
    return last;
}

然后在此基础上写出翻转单链表第m个节点到第n个节点的程序:

struct ListNode* successor = NULL;
struct ListNode* reverseN(struct ListNode* head, int n) {
    if (n == 1) {
        successor = head->next;  // successor记录原链表第n个节点的next
        return head;
    }
    struct ListNode* last = reverseN(head->next, n - 1);
    head->next->next = head;
    head->next = successor;
    return last;
}

struct ListNode* reverseBetween(struct ListNode* head, int m, int n) {
    if (m <= 1) {
        return reverseN(head, n - m + 1);
    }
    head->next = reverseBetween(head->next, m - 1, n - 1);
    return head;
}
Last modification:November 10th, 2019 at 10:20 am