反转链表

题目

力扣第 206 题，反转链表，示例：

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

思路

链表反转的效果如下：

要实现这样的功能，我们的思路是我们使用两个指针，分别为 pre 指向要当前要反转的前一个结点，cur 指向当前要反转的指针，初始化时，我们需要反转第一个结点和第二个结点，因此，此时 pre 指针指向 NULL，cur 指针指向结点 1，那么指针位置如下：

同时，我们在反转时，防止反转结点的丢失，我们需要使用一个辅助指针 temp 保存当前结点的下一个结点，那么，指针的位置如下图所示：

现在，我们只需要将 cur 的 next 指针指向 pre 即可，如下图所示：

接着，我们将 pre 指针指向 cur，如下图所示：

最后，我们把 cur 再次指向 temp，如下图所示：

此时，就完成了第一个结点的反转，现在我们进入第二个结点循环时，直接将 temp 结点后移一位即可，此时，链表结构如下：

此时，我们再次将 cur 的 next 指针指向 pre，如下图所示：

接着，再次将 pre 指向 cur，如下图所示：

最后，我们把 cur 再次指向 temp，如下图所示：

我们看到，第二次循环之后，我们已经完成了两个结点的反转，一直循环到最后一个结点即可。

代码具体实现

C语言版本

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head){
    //初始化时，pre指针为空
    struct ListNode* pre = NULL;
    //cur指针指向head
    struct ListNode* cur = head;
    //如果 cur 指针不为空，则一直循环
    while(cur != NULL){
		//首先，使用 temp 指针保存 cur 结点的下一个结点
        struct ListNode* temp = cur->next;
        //cur的 next 指针指向 pre，也就是反转
        cur->next = pre;
        //pre 指向 cur，也就是实现了将 pre 指针后移一位
        pre = cur;
		// cur 指向 temp，同样，也是实现了 cur 指针的后移
        cur = temp;
    }
    //最后循环结束了，此时 cur 为空了，因此，我们应该返回 pre 结点
    return pre;
}

Java版本

遍历

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        //定义一个当前要被替换的节点，从第二个节点开始
        ListNode currentNode = head.next;
        //被替换的节点的前一个节点
        ListNode preNode = head;
        preNode.next = null;
        while (true) {
            //获取当前节点的下一个节点
            ListNode nextNode = currentNode.next;
            //将前一个节点追加到当前节点后面
            currentNode.next = preNode;
            //遍历循环到最后一个节点
            if (nextNode == null) {
                return currentNode;
            }
            //将当前要操作的节点和前一个节点重新设置，往后挪动指针
            preNode = currentNode;
            currentNode = nextNode;
        }
    }
}

递归

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 在整理思绪的时候，我们会发现前一个节点和后一个节点在进行节点交换的时候，做的事情是一样的将当前节点和后面一个节点交换，然后将当前节点的后指针指向剩下的节点。
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode node1 = head;
        ListNode node2 = head.next;
        node1.next = null;
        ListNode retNode = revertNode(node1, node2);
        return retNode;
    }
    private ListNode revertNode(ListNode node1,ListNode node2){
        ListNode retNode = null;
        //获取剩下的节点，剩下的节点将要和当前节点执行重复操作
        ListNode node3 = node2.next;
        if (node3 != null) {
            //重置当前节点的后一个节点
            node2.next = node1;
            //将当前节点和剩下的节点调换位置
            retNode = revertNode(node2, node3);
        } else {
            node2.next = node1;
            retNode = node2;
        }
        return retNode;
    }
}

Go语言版本

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    //初始化时，pre指针为空
    var pre *ListNode
    //cur指针指向head
    cur := head
    //如果 cur 指针不为空，则一直循环
    for(cur != nil){
        //首先，使用 temp 指针保存 cur 结点的下一个结点
        temp := cur.Next
        //cur的 next 指针指向 pre，也就是反转
        cur.Next = pre
        //pre 指向 cur，也就是实现了将 pre 指针后移一位
        pre = cur
		// cur 指向 temp，同样，也是实现了 cur 指针的后移
        cur = temp
    }
    //最后循环结束了，此时 cur 为空了，因此，我们应该返回 pre 结点
    return pre;
}