每天一道leetcode206-反转链表

题目

leetcode206-反转链表 分类：链表 中文链接： https://leetcode-cn.com/problems/reverse-linked-list/ 英文链接： https://leetcode.com/problems/reverse-linked-list/

题目详述

反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

题目详解

思路

1. 反转链表的话就是需要用三个节点，分别是pre节点代表前一个节点，pNode节点是当前节点，next节点是当前节点的下一个节点;
2. 我的方法是先去处理最开始的那一个节点，也就是头结点，令头结点的next置为空，然后，pre指向头结点，pNode当前节点是指向head.next,next是指向pNode节点的下一个节点；这是初始化操作;
3. 然后接下来的操作就是，先用next保存下来pNode的下一个节点，然后就是pNode指向pre,因为pre是pNode的上一个节点，这样可以让反转，因为这里已经反转完毕了，然后就是就是pre和pNode同时往后面进行移动；
4. 如何移动，很简单就是pre先指向pNode,然后pNode指向next;
5. 最后循环结束的时候，pNode为空，pre是pNode的前一个，pre是最后一个节点，也是就反转后的头结点，最后返回pre即可

代码

/**
 * 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 pre = head;
        ListNode pNode = head.next;
        ListNode next = head;
        //首先处理前两个节点；
        pre.next = null;
        while(pNode != null)
        {
            next = pNode.next;
            pNode.next = pre;
            pre = pNode;
            pNode = next;
        }
        return pre;
    }
}

代码讲解

• 13-17行代码就是处理最开始的第一个节点，令最开始的pre的下一个为null，最开始的节点是反转后的末尾节点，所以应该这样做
• 18-24行就是反转链表的中间部分，对应思路中的3和4
• 25行就是返回pre，也就是新的头结点