JZ15 — 反转链表

题目描述

输入一个链表，反转链表后，输出新链表的表头。

题目分析

这个题目的意思其实是在原链表上直接进行反转。
其实也很简单，只要稍微注意一下临界位置的处理即可。
主要思路：
遍历原链表
1. 执行pnext = pHead->next，记录当前结点pHead的后一个结点*pnext
2. 执行pHead->next = pre，将当前结点的next指向前一个结点，实现反转。
3. 当前结点已经反转完成，需要指向下一个结点了。首先执行pre = pHead，将当前结点赋值给pre，成为下一个结点的前一个结点。然后执行pHead = pnext，将pHead指向下一个结点。

C++

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution
{
public:
    ListNode *ReverseList(ListNode *pHead)
    {
        ListNode *pre = NULL, *pnext;
        while (pHead)
        {
            pnext = pHead->next;
            pHead->next = pre;
            pre = pHead;
            pHead = pnext;
        }
        return pre;
    }
};

Java

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode pre = null, pnext;
        while (head != null) {
            pnext = head.next;
            head.next = pre;
            pre = head;
            head = pnext;
        }
        return pre;
    }
}