206.反转链表🔖链表

206. 反转链表

• https://leetcode-cn.com/problems/reverse-linked-list/

  问题描述

  

  问题思路

1. 利用外部空间：将所给链表存到ArryList里面或者是新的链表里面，然后再反转动态数组就可以了。
2. 快慢指针

3. 递归解法

   代码实现

   js

   /**
   * Definition for singly-linked list.
   * function ListNode(val, next) {
   *     this.val = (val===undefined ? 0 : val)
   *     this.next = (next===undefined ? null : next)
   * }
   */
   /**
   * @param {ListNode} head
   * @return {ListNode}
   */
   var reverseList = function(head) {
    let prev = null;
    let curr = head;
    while (curr) {
        const next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
   };

   递归实现

   /**
   * public class ListNode {
   *     int val;
   *     ListNode next;
   *     ListNode(int x) { val = x; }
   * }
   */

   // 避免陷入死循环
   if (head == null || head.next == null) return head;
   ListNode newHead = reverseList(head.next); //此处递归，找到最后一个节点了
   head.next.next = head; //重新指定节点指向（有两个next，注意少写）
   head.next = null; //将最初的节点指向空
   return newHead; //返回新的“倒置”头节点

   快慢指针

   class Solution {
    public ListNode reverseList(ListNode head) {
        // 避免陷入死循环
        if (head == null || head.next == null) return head;
        ListNode newHead = null;
        while (head != null){
            ListNode tmp = head.next;
            head.next = newHead;
            newHead = head;
            head = tmp;
        }
        return newHead;
    }
   }