leetcode-单链表反转

Question

反转一个单链表。

示例:

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

力扣的链接如下：
206. 反转链表

我用迭代法写出的代码如下

class Solution {

public ListNode reverseList(ListNode head) {
    if(head == null || head.next == null){
        return head;
    }
    ListNode newNode = null;
    while(head != null){
        ListNode tempNode = head;
        tempNode.next = newNode;
        newNode = tempNode;
        head = head.next;
    }
    return newNode;
}

}

请问，问题出在哪里了？
我的思路是遍历原来的链表，然后把每个节点插入一个新的链表，最后返回那个新的链表。

Answer 1

tempNode.next = newNode;

head = head.next;

仔细品你的这两句。前一句把head.next置空，后一句又来取next

稍微修改一下：

public ListNode reverseList(ListNode head) {
    if(head == null){
        return head;
    }
    ListNode newNode = null;
    while(head != null){
        ListNode tempNode = newNode;
        newNode = head;
        head = head.next;
        newNode.next = tempNode;
    }
    return newNode;
}

相当于两个相邻指针逐步向右移动，最主要的是要注意指针移动的顺序。先用临时变量tmp记录下左指针的位置，然后移动左指针到右指针位置，然后移动右指针到下一个位置，再把左指针的next志向tmp。