L1-翻转链表

翻转一个链表

样例
给出一个链表1->2->3->null，这个翻转后的链表为3->2->1->null

递归方法

java

/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */   
public class Solution {
/**
     * @param head: n
     * @return: The new head of reversed linked list.
   */ 
    public ListNode reverse(ListNode head) {
        // write your code here
    	if(head==null||head.next==null) return head;
    	ListNode second=head.next;
    	head.next=null;
    	ListNode rs=reverse(second);
    	second.next=head;
    	return  rs;
    }
}

python

"""
Definition of ListNode

class ListNode(object):

    def __init__(self, val, next=None):
        self.val = val
        self.next = next
"""
class Solution:
    """
    @param head: The first node of the linked list.
    @return: You should return the head of the reversed linked list. 
                  Reverse it in-place.
    """
    def reverse(self, head):
        # write your code here
        if head == None or head.next == None:
            return head 
        second = head.next;
        head.next = None 
        res = self.reverse(second)
        second.next = head
        return res

非递归方法

定义三个节点：

newhead翻转后的头节点

p向前走的节点

prev要插入节点的前一个节点，同时在循环中还有一个节点pNext临时保存p的下一个节点

初始值：p=head,prev = null,newead = null

在循环中：

先pNext = p.next 临时保存p的下一个节点，防止链表断链

p.next = prev p的下一个节点直线prev节点，就是翻转，链接到其前面的一个节点，为了保持每次都能这样链接

prev = p prev节点向后移动一个节点

最后p = pNext 循环下去

同时要找到链表的头节点

当p.next==null的时候 newHead = p p就是头节点,其实运行结束时候的prev节点就是指向头节点的，单独搞个头节点，看着舒服点

java

/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */   
public class Solution {
/**
     * @param head: n
     * @return: The new head of reversed linked list.
   */ 
    public ListNode reverse(ListNode head) {
        // write your code here
        	ListNode p=head,pre=null,pnext=null,newHead=null;
    	while(p!=null)
    	{
    		if(p.next==null)newHead=p;
    		pnext=p.next;
    		p.next=pre;
    		pre=p;
    		p=pnext;
    		
    	}
    return newHead;
    	}
}

python

"""
Definition of ListNode

class ListNode(object):

    def __init__(self, val, next=None):
        self.val = val
        self.next = next
"""
class Solution:
    """
    @param head: The first node of the linked list.
    @return: You should return the head of the reversed linked list. 
                  Reverse it in-place.
    """
    def reverse(self, head):
        # write your code here
        p = head 
        prev = None
        revHead = None
        while p!=None:
            pNext = p.next
            if pNext ==None:
                revHead = p
            p.next = prev
            prev = p
            p = pNext
        return revHead