链表的题目比较直观,如果不会做,可以动手画一画,模拟一下步骤,把步骤转换成代码就可以做出来了。

一、迭代

Solution1

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode newHead = null;
        while(head != null){
            ListNode nextNode = head.next;
            head.next = newHead;
            newHead = head;
            head = nextNode;
        }
        return newHead;
    }
}

这个方法是把原链表的结点一个一个地拆下来,然后连接到新的链表头newHead中。
按照步骤走一遍,下面结合代码和例子说明。
以1->2->3->4->5->NULL为例:

  1. 明确指针的指向:head指针用于遍历原链表,newHead作为未来结果的头指针返回。

head ->1->2->3->4->5->NULL
newHead ->NULL

  1. while中的第一遍:

nextNode保存head(1)的下一个结点(2),防止丢失原链表,因为下面直接用head进行操作。
把当前head结点(1)的next指向了newHead(null),并把head指向的结点(1)作为新的头结点。
最后把nextNode(2)赋回给head,继续接下来的遍历。
所以,经过一轮遍历后,现在链表的情况变成这样:
head->2->3->4->5->NULL
newHead ->1 ->NULL

  1. while中的第二遍:

nextNode保存head(2)的下一个结点(3)。
把head指向的结点(2)的next指向newHead,即2->1->NULL(此时newHead指向1)。然后让newHead指向2。
最后再让head指向newHead,继续遍历。
此时指针指向
head->3->4->5->NULL
newHead->2 ->1 ->NULL
……

由此看来,就是把链表上的结点一个一个地拆下来,然后再一个一个地拼到新链表newHead中。

Solution2

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        } 
        ListNode pre = null, cur = head;
        while(cur != null){
            ListNode node = cur.next;
            cur.next = pre;
            /*
            if(node == null){
                break;
            }
            */
            pre = cur;
            cur = node;
        }
        // return cur;
        return pre;
    }
}

这个做法与Solution1有点不同,它是直接把指针的转向给翻转,遍历的时候修改了next指针,同时并保存当前遍历的位置与链表。ummmm说得还是有点奇怪,下面举例手动debug一下。

  1. 双指针pre和cur:pre表示指向当前结点的前一个结点,cur表示当前结点。由于是遍历的时候修改next区域,会导致链表断开,所以需要保存好结点信息。
  2. 从正常的遍历到中间的结点开始说起。

1<-2<- pre cur->3->4->5->NULL
可见pre前面的已经完成,然后指向结点2,cur指向当前结点。
因为要修改cur的next域,所以要先保存cur当前的next域,不然就会丢失原链表了,所以对应代码为ListNode node = cur.next;
然后修改cur的next域,指向前一个结点pre。cur.next = pre;
结点3的反转已经完成,所以接下来继续向前遍历,处理pre和cur域的值。

  1. 其实里面的变换很简单,只要理清楚指向的变换以及它的思想就可以了。

PS:我真的好傻,注释中的是我第一次写的想法,但觉得好冗余,无端端多了个if在这碍事,还是要多想……虽然把步骤变成代码可以解决大部分情况,但对于特殊的情况还是要细细思考,特别是边界条件。

Solution3

其实并不是活生生地对一道题目创造出多种解法,一题多解对于以后的拓展很有帮忙,说不定下一道题用就是要用这方法才方便解决呢?也说不定……(手动滑稽,去做做反转链表2吧)

简单地说,就是把后面的元素一个一个地删除,然后放到链表头中。
我们设定一个头结点dummy,再设定一个cur指针指向第一个结点(即初始情况下,head指向的结点)。
把cur的下一个结点删除掉,放到头结点的后面。
循环这个动作。

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        } 
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy, cur = head;
        while(cur != null && cur.next != null){
            ListNode node = cur.next;
            // 删除这个结点
            cur.next = node.next;
            // 把它插入到dummy的后面
            node.next = pre.next;
            pre.next = node; 
        }
        return dummy.next;
    }
}