题解 | #反转链表#JAVA/C++/Go/Python

反转链表

http://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca

反转链表迭代版本和非迭代版本,支持流行的四种语言

JAVA

public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode res=null;
        ListNode p=head;
        while(p!=null)
        {
            ListNode nextNode=p.next;
            p.next=res;
            res=p;
            p=nextNode;
        }
        return res;
    }
}

迭代版本

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode prehead = ReverseList(head.next);
        head.next.next = head;
        head.next = null;
        return prehead;
    }
}

C++

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead==NULL||pHead->next==NULL){
            return pHead;
        }
        ListNode* preHead = ReverseList(pHead->next);
        pHead->next->next = pHead;
        pHead->next =NULL;
        return preHead;       
    }
};

迭代版本

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode* res = NULL;
        for(ListNode* p = pHead;p!=NULL;){
            ListNode* next = p->next;
            p->next = res;
            res = p;
            p = next;            
        }
        return res;
    }
};

Go

package main
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 
 * @param pHead ListNode类 
 * @return ListNode类
*/
func ReverseList( pHead *ListNode ) *ListNode {
    // write code here
    if pHead == nil || pHead.Next == nil{
        return pHead
    }
    preHead := ReverseList(pHead.Next)
    pHead.Next.Next = pHead
    pHead.Next = nil
    return preHead
}

迭代版本

func ReverseList( pHead *ListNode ) *ListNode {
    // write code here
    var res *ListNode
    for pHead != nil {
        next:=pHead.Next
        pHead.Next = res
        res = pHead
        pHead = next
    }
    return res;
}

Python

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        res = None
        while pHead:
            nextNode = pHead.next
            pHead.next = res
            res = pHead
            pHead = nextNode
        return res
        # write code here

迭代版本

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        if pHead is None&nbs***bsp;pHead.next is None:
            return pHead
        preHead = Solution.ReverseList(self,pHead.next)
        pHead.next.next = pHead
        pHead.next = None
        return preHead