大家好，这里是小编的博客频道
小编的博客：就爱学编程

很高兴在CSDN这个大家庭与大家相识，希望能在这里与大家共同进步，共同收获更好的自己！！！

---

废话不多说，我们直接看题。

1.反转链表

（1）题目描述

---

（2）解题思路

迭代

• 假设链表为 1→2→∅，我们想要把它改成 ∅←1←2。

具体思路：

• 在遍历链表时，将当前节点（cur）的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点，这里小编用prev。在更改引用之前，还需要存储后一个节点,，这里小编用next。最后返回新的头引用，不难想到就是迭代到最后的prev指针。

代码实现：

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;
    while (curr) {
        struct ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

（3）复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次。

• 空间复杂度：O(1)。

---

2.链表的中间节点

（1）题目描述

---

（2）解题思路

快慢指针

• 用两个指针 slow与 fast 一起遍历链表。slow 一次走一步，fast 一次走两步。那么当 fast 到达链表的末尾时，slow 必然位于中间。

代码：

struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* slow = head, * fast = head;
    while(fast){
        if(fast->next == NULL){
            break;
        }
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

注意：

• 这里还得考虑链表仅有一个节点的情况，所以做了特殊处理。

（3）复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次（快慢指针遍历次数之和）。

• 空间复杂度：O(1)。

---

3.返回倒数第K个节点

（1）题目描述

---

（2）解题思路

先后指针

双指针，一个指针p2先走k步，然后两个(p1,p2)一起走。又题目说k是有效的，所以就没有判断先走的指针p2是否越界

代码实现：

int kthToLast(struct ListNode* head, int k) {
    struct ListNode* slow = head, * fast = head;
    while(k--){
        fast = fast->next;
    }
    while(fast){
        fast = fast->next;
        slow = slow->next;
    }
    return slow->val;
}

（3）复杂度分析

时间复杂度: O(n)

空间复杂度: O(1)

---

4.合并两个有序链表成一个新的有序链表（相对）

（1）题目描述

---

（2）解题思路

双指针 + 哨兵位

• 首先，我们设定一个哨兵节点 dummy，这可以在最后让我们比较容易地返回合并后的链表。我们维护一个 cur指针，我们需要做的是调整它的next指针。然后，我们重复以下过程，直到 list1 或者 list2指向了 NULL：如果 list1 当前节点的值小于等于 list2，我们就把 list1 当前的节点接在 cur节点的后面同时将 list1 指针往后移一位。否则，我们对 list2 做同样的操作。不管我们将哪一个元素接在了后面，我们都需要把 cur向后移一位。

• 在循环终止的时候， l list1和 list2 至多有一个是非空的。由于输入的两个链表都是有序的，所以不管哪个链表是非空的，它包含的所有元素都比前面已经合并链表中的所有元素都要大。这意味着我们只需要简单地将非空链表接在合并链表的后面，并返回合并链表即可。

代码实现：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
   struct ListNode dummy = {};
   struct ListNode* cur = &dummy;             //建立哨兵位
   while(list1 && list2){
    if(list1->val > list2->val){
        cur->next = list2;
        list2 = list2->next;
    }
    else{
        cur->next = list1;
        list1 = list1->next;
    }
    cur = cur->next;
   }
   cur->next = list1 ? list1 : list2;		//链接剩余部分
   return dummy.next;
}

（3）复杂度分析

复杂度分析

时间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。

空间复杂度：O(1)。

---

5.链表分割

（1）题目描述

---

（2）解题思路

双指针 + 双哨兵位

• 我们只需维护两个链表 dummy1 和 dummy2 即可，dummy 链表按顺序存储所有小于x的节点，dummy2 链表按顺序存储所有大于等于x的节点。遍历完原链表后，我们只要将 dummy1 链表尾节点指向 dummy2 链表的头节点即能完成对链表的分割。

代码实现：

struct ListNode* partition(struct ListNode* head, int x) {
    struct ListNode dummy1 = {}, dummy2 = {};
    struct ListNode* cur1 = &dummy1, * cur2 = &dummy2, * fail = head;
    while(fail){
        //把大于等于x的节点放在一个链表1中
        if(fail->val >= x){
            cur1 = cur1->next = fail;
        }
        //把小于x的节点放在另一个链表2中
        else{
            cur2 = cur2->next = fail;
        }
        fail = fail->next;
    }
    //合并链表
    cur2->next = dummy1.next;
    cur1->next = NULL;
    return dummy2.next;
}

（3）复杂度分析

时间复杂度: O(n)。

空间复杂度: O(1)。

---

6.回文链表

（1）题目描述

---

（2）解题思路

我们可以将链表的后半部分反转（修改链表结构），然后将前半部分和后半部分进行比较。比较完成后我们应该将链表恢复原样。

整个流程分为4个步骤：

• 1.找到前半部分链表的尾节点。
• 2.反转后半部分链表。
• 3.判断是否回文。
• 4.恢复链表。

代码实现：

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;
    while (curr != NULL) {
        struct ListNode* nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

struct ListNode* endOfFirstHalf(struct ListNode* head) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while (fast->next != NULL && fast->next->next != NULL) {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

bool isPalindrome(struct ListNode* head) {
    if (head == NULL) {
        return true;
    }

    // 找到前半部分链表的尾节点并反转后半部分链表
    struct ListNode* firstHalfEnd = endOfFirstHalf(head);
    struct ListNode* secondHalfStart = reverseList(firstHalfEnd->next);

    // 判断是否回文
    struct ListNode* p1 = head;
    struct ListNode* p2 = secondHalfStart;
    bool result = true;
    while (result && p2 != NULL) {
        if (p1->val != p2->val) {
            result = false;
        }
        p1 = p1->next;
        p2 = p2->next;
    }

    // 还原链表并返回结果
    firstHalfEnd->next = reverseList(secondHalfStart);
    return result;
}

（3）复杂度分析

时间复杂度：O(n)。

空间复杂度：O(1)。我们只会修改原本链表中节点的指向，而在堆栈上的堆栈帧不超过 O(1)。

---

快乐的时光总是短暂，咱们下篇博文再见啦！！！如果小编的文章会对你有帮助的话不要忘了，记得给小编点点赞和收藏支持一下，在此非常感谢！！！