avatar

leecode-206-反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?

Related Topics
  • 链表
  • \n
  • 👍 1696
  • 👎 0
  • 解法1:迭代

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    //反转一个单链表。 
    //
    // 示例:
    //
    // 输入: 1->2->3->4->5->NULL
    //输出: 5->4->3->2->1->NULL
    //
    // 进阶:
    //你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
    // Related Topics 链表
    // 👍 1696 👎 0


    //leetcode submit region begin(Prohibit modification and deletion)
    /**
    * Definition for singly-linked list.
    * public class ListNode {
    * int val;
    * ListNode next;
    * ListNode() {}
    * ListNode(int val) { this.val = val; }
    * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    * }
    */
    class Solution {
    public ListNode reverseList(ListNode head) {
    // 迭代 翻转的关键在于将后节点改成前节点
    ListNode prev = null;
    ListNode curr = head;
    while(curr != null){
    ListNode next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
    }
    return prev;
    }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    解法二:递归

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    //反转一个单链表。 
    //
    // 示例:
    //
    // 输入: 1->2->3->4->5->NULL
    //输出: 5->4->3->2->1->NULL
    //
    // 进阶:
    //你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
    // Related Topics 链表
    // 👍 1696 👎 0


    //leetcode submit region begin(Prohibit modification and deletion)
    /**
    * Definition for singly-linked list.
    * public class ListNode {
    * int val;
    * ListNode next;
    * ListNode() {}
    * ListNode(int val) { this.val = val; }
    * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    * }
    */
    class Solution {
    public ListNode reverseList(ListNode head) {
    //递归
    if (head == null || head.next == null) {
    return head;
    }
    ListNode newHead = reverseList(head.next);
    //将后节点的值改成前节点,关键点还有,head的后节点注意置空
    head.next.next = head;
    head.next = null;
    return newHead;
    }
    }
    //leetcode submit region end(Prohibit modification and deletion)
    文章作者: 无知的小狼
    文章链接: https://bytedance.press/2021/04/21/20210401/leecode-206-%E5%8F%8D%E8%BD%AC%E9%93%BE%E8%A1%A8/
    版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 无知的小狼

    评论