茄子算法每日N题之LeetCode206反转链表

LeetCode 206.反转链表

大家好，我是灵魂画师–茄子。技术水平一般，喜欢画画。

开始今天的正题。

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

leetCode206题反转链表

神三元同学的前端算法练习指南

解题思路：
1.双指针迭代

图解：

题解：我们先设立2个指针 1个pre先指向null 第二个 cur指向head

1. (cur现在是第一项) 先让cur的下一项指向pre (把第一项变为 1->2->3->4->5->NULL 变为 1->NULL)
2. 让pre和cur都向前前进1位。 pre 为置换后的cur cur为置换前的cur.next。

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
let reverseList =  (head) => {
    let pre = null;
    let cur = head;
    while(cur != null){
// 先把 next = 2->3->4->5->NULL 
       let next = cur.next;
// 然后让 cur.next赋值为NULL((cur目前是 1->2->3->4->5->NULL 赋值之后 1->NULL)
        cur.next = pre;
// pre 进一位 pre原来是 null 进一位 ({1,next:{null}})
        pre = cur;
// cur 原来是 1->2->3->4->5->NULL  进一位 2->3->4->5->NULL
        cur = next;
    }

    return pre;
};

2.暴力解法

题解：

暴力拆解嘛，就文字描述把 就不画图了。创建一个array 遍历head 将head的每一项拿出来，反转。然后再遍历这俩，填回去。(目前还没写完 暴力解法有点麻烦。。。)

var head = {val:1,next:{val:2,next:{val:3,next:null}}}

let reverseList =  (head) => {
    let arr = arrSwitch(head,[])
    // 刚刚遍历拿出来 还啥也没干暂停
    function arrSwitch(head,arr){
        if(arr.length != []){
          return  reverseArrList(arr)
        } else {
          return  arrList(head,arr)
        }
    }
    function arrList(head,arr){
        let cur = head;
        while(cur != null){           
            arr.push(cur.val); // push当前项[1]
            cur = cur.next //
        }
        return arr
    }
    function reverseArrList(arr){
        // 这里反转遍历填回去然后返回
    }
};


reverseList(head)

1. 递归解法

/**
 * @param {ListNode} head
 * @return {ListNode}
 * 可以理解为cur为下一项 每一次去除头部 
 * pre为反转后的 每一次把反转后的添加上
 */
let reverseList =  (head) => {
    let reverse = (pre,cur)=>{
        if(!cur){
            return pre;
        }
    // next => 2->3->4->5->NULL 
        let next = cur.next 
    // cur.next => NULL
        cur.next = pre
    // pre => 1
        pre = cur
    // cur => 2->3->4->5->NULL 
        cur = next
        reverse(pre,cur)
    }
    return reverse(null, head);
};

1. 递归解法2

/**
 * @param {ListNode} head
 * @return {ListNode}
 * 拆解
 * 1 -> 2 -> 3 -> 4 -> 5 -> NULL
 * 1 -> reverseList(2 -> 3 -> 4 -> 5-> NULL)
 * 1 -> reverseList(2 -> reverseList(3 -> 4 -> 5 -> NULL))
 * ...
 * 1 -> reverseList(2 -> reverseList(3 -> reverseList(4 -> reverseList(5 -> NULL))))
 * 1 -> reverseList(2 -> reverseList(3 -> reverseList(4 -> 5))) // reverseList(5 -> NULL)由于if(head.next == null) 返回了5
 * 1 -> reverseList(2 -> reverseList(3 -> (4 <- 5))) // head.next.next = head // 5 指向4  4指向NULL
                                           |
                                          NULL 
    1 -> reverseList(2 -> (3 <- 4 <- 5)) // head.next.next = head // 4 指向3  3指向NULL 
                           |    X
                          NULL NULL 
    1 -> reverseList(2 <-  3 <-  4 <- 5) // head.next.next = head // 3 指向2  2指向NULL 
                     |     X     X
                    NULL  NULL  NULL 
    1 <- 2 <-  3 <-  4 <- 5 // head.next.next = head // 2 指向1  1指向NULL 
    |    X     X     X
   NULL  NULL  NULL  NULL 
   
   NULL <- 1 <- 2 <- 3 <- 4 <- 5
 */
let reverseList =  (head) => {
    if(head.next == null){
        return head
    }
    let lest = reverseList(head.next);
    head.next.next = head
    head.next = null
    return lest
};

以上就是我的思路以及解法了，希望大家喜欢我画的图解，我会继续努力的ヾ(◍°∇°◍)ﾉﾞ。