lintcode 32 翻转链表

image.png

• 思路

  
  image.png
  

  每次遍历的节点拿到最前面，作为新的head节点。

head=p.next

那么2节点的next地址不能丢了。
p.next=head.next
然后考虑2的后面是谁？
head.next=q
如果没有这个q，head.next=p。第三个节点出现的时候，就会把中间的丢了。因为每次新出来的节点要连接上次出来的点。需要有个引用指向它。p指向顺序遍历的尾节点。head是每次出来的那个点。q用来指向head需要连接到的点

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param head: The head of linked list.
     * @return: The new head of reversed linked list.
     */
    public ListNode reverse(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode p = head;
       ListNode q = head;
        while(p.next!= null){
           head=p.next;
           p.next=head.next;
           head.next=q;
           q=head;           
        }
        return head;
    }
}