206. 反转链表

难度：中等

题目

反转一个单链表。

示例：

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶：

你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

Reference

题解

基本思路： 只需要将链表结构中的所有指针反转，即指向前一节点的指针现在指向后一节点。定义两个指针指向需要反转部分的两个节点，将后一指针的next域指向前一指针。改反转操作破坏了后一指针原有的next域，需要一个额外的指针用于向前移动。

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* reverseList(struct ListNode* head){
    if (!head || !(head->next))
        return head;
    struct ListNode *cur1 = head, *cur2 = head->next, *cur3 = cur2->next;
    head->next = NULL;
    while (cur3)
    {
        cur2->next = cur1;
        cur1 = cur2;
        cur2 = cur3;
        cur3 = cur3->next;
    }
    cur2->next = cur1;
    return cur2;
}

评论