题解 | #反转链表#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
