ReverseLinkedListOPT [source code]

public class ReverseLinkedListOPT {
    public ListNode reverseList(ListNode head) {
        if (head == null) return null;
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}

这个是 submission 最优解, 0ms;

这个算法实际操作的时候, 做的工作也是把 list 截成两段, 然后左边这一段一个一个的移动到右边的这一段, 如果看不出来, 可以自己画一个图试试看;

这个题目暴露出来我对指针的理解的不深入;

比如: 1 -> 2 -> 3 -> 4
这样一个 list, 假如别人要给你 access to head, 其实就是比如给了你一个head = * 1这样的意思; 但是这个你要理解一个问题, 不能认为 head 就等于1这个 node 了. head 本身应该 visualize 成一个类似箭头的东西, 一个箭头指着1. 这个箭头现在是指着1的, 但是不代表永远可以指着1.

指针本身只是一个箭头, 如果我们用pointer.attribute, 比如head.val的时候, 属于调用, 那么这个时候你可以直接就把 head 本能的当成是node 1一样的使用.
但是如果是一个赋值 assignment 操作, 比如head = *2这样的操作的时候, 你就不能认为说是node 1 = node 2了, 因为我们在 assignment 的时候变动的只是这个箭头自己而已;

类似的, 1.next = 3这个并不是把2变成了3, 而是把1的 child 箭头换了一个指向对象而已;

感觉涉及到这种recursive structure的指针操作我还是有待锻炼;

/**

• Definition for singly-linked list.
• public class ListNode {
• int val;
• ListNode next;
• ListNode(int x) { val = x; }
• }
  */

Problem Description

Reverse a singly linked list.

click to show more hints.

Hint:
A linked list can be reversed either iteratively or recursively. Could you implement both?

Difficulty:Easy
Category:Algorithms
Acceptance:45.04%
Contributor: LeetCode
Companies
uber facebook twitter zenefits amazon microsoft snapchat apple yahoo bloomberg yelp adobe
Related Topics
linked list
Similar Questions
Reverse Linked List II Binary Tree Upside Down Palindrome Linked List