206. 反转链表
1. 题目形容
<p> 反转一个单链表。</p><br/><p>示例:</p><br/><pre>输出: 1->2->3->4->5->NULL<br/>输入: 5->4->3->2->1->NULL</pre><br/><p>进阶:
<br/> 你能够迭代或递归地反转链表。你是否用两种办法解决这道题？</p><br/>
2. 解题报告
思路 1：借助栈
利用栈先进后出的特点，将每个节点按程序存入栈中，再从顶到底连贯栈中的每个节点
留神要将翻转后的最初一个节点（即原链表的第一个节点）的 next 置为 nullptr，不然结果可想而知~
思路 2：就地操作（举荐）
一一断开原链表的每个节点（保留下个节点）
将断开的节点连贯到反转链表的表头上
更新反转链表的表头
回到原链表的下个节点
3. 最优答案
c 答案
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
//struct ListNode* reverseList(struct ListNode* head) {
// struct ListNode* new = NULL;
// while(head) {
// struct ListNode* temp = head;
// head = head->next;
// temp->next = new;
// new = temp;
// }
// return new;
//}
struct ListNode* reverseList(struct ListNode* head) {if (!head || !head->next) return head;
struct ListNode *L = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return L;
}
c++ 答案
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {if (!head || !head->next) return head;
ListNode *node = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return node;
}
};
java 答案
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {val = x;}
* }
*/
class DIYStack{public ArrayList<Integer> container = new ArrayList<>();
public void comeIn(int item){container.add(item);
}
public int comeOut(){return container.remove(container.size()-1);
}
}
class Solution {public ListNode reverseList(ListNode head) {DIYStack diyStack = new DIYStack();
ListNode tmp = head;
while (tmp != null){diyStack.comeIn(tmp.val);
tmp = tmp.next;
}
tmp = head;
while (tmp != null) {tmp.val = diyStack.comeOut();
tmp = tmp.next;
}
return head;
}
}
JavaScript 答案
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
var cur = head;
var prev = null;
while(cur){
var next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
};
c# 答案
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) {val = x;}
* }
*/
public class Solution {public ListNode ReverseList(ListNode head) {
ListNode b = null;
ListNode Nextindex;
while(head != null)
{
Nextindex = head.next;
head.next = b;
b=head;
head = Nextindex;
}
return b;
}
}
python2.x 答案
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None or head.next is None:
return head
stack = []
while head:
stack.append(head)
head = head.next
newHead = stack[-1]
# while stack:
# now = stack.pop()
for i in range(len(stack) - 1, 0, -1):
stack[i].next = stack[i - 1]
stack[0].next = None
return newHead
python3.x 答案
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None:
return None
if head.next is None:
return head
p = head
q = None
while p:
tmp = p.next
p.next = q
q = p
p = tmp
return q
go 答案
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
var preNode *ListNode = nil
var currentNode *ListNode = head
for currentNode != nil {
nextNode := currentNode.Next
currentNode.Next = preNode
preNode = currentNode
currentNode = nextNode
}
return preNode
}
4.leetcode 解题报告合集
leetcode 最佳答案：
leetcode 是练习算法能力修炼编程内功十分好的平台，然而官网上解题报告不全，网上的答案也有对有错，为了晋升大家刷题的效率，现将每个题目的各种语言的答案 (通过测试) 总结公布进去，供大家参考。每个题目蕴含 c、c++、java、python、python3、javascript、c#、go 8 种常见语言的答案。