关于java:2021字节跳动校招秋招算法面试真题解题报告leetcode206-反转链表内含7种语言答案

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 种常见语言的答案。