翻转链表

给定头节点，翻转链表

CPP

思路一：设置双指针进行翻转

需要保存的节点：

• pre指针：指向当前指针需要进行翻转的位置；
• cur指针：指向当前操作的节点；
• temp指针：用于保证能访问断开链表之后的指针。

因此，终止条件就是cur指针指向空节点时跳出循环； 而此时 pre指针恰好指向翻转节点的末尾。即需要return这个。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = head;
        ListNode* pre = nullptr;
        ListNode* temp;
        while (cur) {
            temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre; //想好要return什么
    }
};

二刷思路一：

还是需要确定当前指针指向哪个位置，整体循环才结束。

[[include]] <iostream>
[[include]] <vector>
using namespace std;

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)
    {
        if (head == nullptr)
            return nullptr;
        ListNode *cur = head;
        ListNode *prev = nullptr;
        ListNode *curnext = cur->next;
        // 在最后一层循环中，cur将移动为nullptr，而这时也应该跳出循环
        while (cur)
        {
            cur->next = prev;
            prev = cur;
            cur = curnext;
            // 最后一层循环，cur要变成nullptr，说明此时next就是nullptr，不能再用空指针
            if (curnext)
                curnext = curnext->next;
        }
        // 此时自然是prev不为空，且指向最后一个元素
        return prev;
    }
};

int main()
{
    Solution s;
    ListNode *head = new ListNode(1);
    ListNode *cur = head;
    for (int i = 2; i <= 5; i++)
    {
        cur->next = new ListNode(i);
        cur = cur->next;
    }
    cur = head;
    while (cur != nullptr)
    {
        cout << cur->val << " ";
        cur = cur->next;
    }
    cout << endl;
    cur = s.reverseList(head);
    while (cur != nullptr)
    {
        cout << cur->val << " ";
        cur = cur->next;
    }
    cout << endl;
}

Java

思路一：双指针

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        // 链表长度为 0, 1时需要直接返回
        if (head == null || head.next == null) {
            return head;
        }
        ListNode cur = head;
        ListNode Tnext = cur.next;
        ListNode temp;
        cur.next = null;
        while (Tnext.next != null) {
            temp = Tnext.next;
            Tnext.next = cur;
            cur = Tnext;
            Tnext = temp;
        }
        Tnext.next = cur;
        return Tnext;
    }
}

思路二：递归实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    ListNode curHead = null;

    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return head;
        }
        reverse(head, head.next);
        return curHead;
    }

    public ListNode reverse(ListNode left, ListNode right) {
        if (right == null) {
            curHead = left;
            return left;
        }
        reverse(right, right.next);
        right.next = left;
        left.next = null;
        return null;
    }
}