2019 算法面试相关(leetcode)--数组和链表

2019-01-08 本文已影响2人 Theendisthebegi

链表和数组作为算法中的两个基本数据结构，在程序设计过程中经常用到。尽管两种结构都可以用来存储一系列的数据，但又各有各的特点。
数组的优劣势：可以方便的遍历查找需要的数据，时间复杂度为O(1)。这种时间上的便利性，是因为数组在内存中占用了连续的空间，在进行类似的查找或者遍历时，本质是指针在内存中的定向偏移。然而，当需要对数组成员进行添加和删除的操作时，数组内完成这类操作的时间复杂度则变成了O(n)
链表的优劣势：在某些操作上比数组更加高效，例如当进行插入和删除操作时，链表操作的时间复杂度仅为O(1)。因为链表在内存中不是连续存储的，所以可以充分利用内存中的碎片空间。
提到数组就不得不提到数组的排序：七种常见的数组排序算法整理(C语言版本)

下面主要针对leetcode上关于链表的一些题目，这里我是使用的JavaScript

function ListNode(val) {
    this.val = val;
    this.next = null;
}

一、3种方法实现反转链表

中文版地址:https://leetcode-cn.com/problems/reverse-linked-list/
1、递归实现
递归的方法其实是非常巧的，它利用递归走到链表的末端，然后再更新每一个node的next 值，实现链表的反转。而newhead 的值没有发生改变，为该链表的最后一个结点，所以，反转后，我们可以得到新链表的head。

var reverseList = function(head) {
   
    if (!head || !head.next) return head;
    
    let newHead = reverseList(head.next);
    
    head.next.next = head;
    
    head.next = null;
    
    return newHead;
};

2、新建链表，头节点插入法
新建一个头结点，遍历原链表，把每个节点用头结点插入到新建链表中。最后，新建的链表就是反转后的链表。

var reverseList = function(head) {

    if (!head || !head.next) return head;

    let lastNode = new ListNode(head.val), curNode;

    let node = head.next;

    while (node) {

        curNode = new ListNode(node.val);

        curNode.next = lastNode;

        lastNode = curNode;

        node = node.next;
    }

    return curNode;
};

3、直接反转
把当前链表的下一个节点指向当前结点，直至循环结束

var reverseList = function(head) {
    
    if(!head || !head.next) return head

    let pre = head, cur, last = head.next;

    head.next = null;

    while (last) {

        cur = last;

        last = cur.next;

        cur.next = pre;

        pre = cur;
    }

    return cur;
};

二、两两交换链表中的节点
记录相邻两个结点cur和last，以及之前的结点prev，然后去进行反转相邻的两个结点，依次循环到最后

var swapPairs = function(head) {
    
    if(!head || !head.next) return head
    
    let res = head.next

    let cur = head

    let prev = last = null

    while(cur && cur.next){

        last = cur.next

        cur.next = last.next

        last.next = cur

        if(prev) prev.next = last

        prev = cur

        cur = cur.next
    }

    return res
};

三、环形链表
正常链表都是有头有尾的，而环形链表则是没有尾的，它的尾会指向其中一个结点(不一定是指向头结点)，也就是环形链表，该题目就是来判断一个链表是否是环形链表。
正常来说，对链表进行循环，如果存在尾指针，即某结点指向null，即可证明该链表不是环形链表。但如果对环形链表进行循环的话，会造成死循环，这样就没办法确定是链表足够长还是该链表是环形链表。

1、比较容易想到的就是利用数组(或集合):循环链表，将结点依次保存在数组中，如果下个结点已经在数组中存在，则说明是环形链表。如果循环到最后指向null，则非环形链表。

var hasCycle = function(head) {
    
    let nodes = []

    while(head){

        if(nodes.indexOf(head)) return true

        nodes.push(head)

        head = head.next
    }

    return false
};

2、还有一种比较巧妙的方法:快慢指针
快慢指针中的快慢指的是移动的步长，即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2，慢指针每次向前移动1次。此外还有其他不少巧妙的应用。

//这里使用快慢指针，slow每次走一步，fast每次走两步，如果不是环形链表，则会一直循环下去，永远不会相遇，直至循环结束。
//反之如果这两个指针相遇，则说明该链表是环形链表。
var hasCycle = function(head) {
    
    let slow = fast = head

    while(fast && fast.next){

        slow = slow.next

        fast = fast.next.next

        if(slow == fast) return true
    }

    return false
};

四、环形链表 II
题目意思是如果链表是环形链表，就返回交点(链表尾连接到链表中的位置)在该链表中的位置，否则返回null
如果是用方法1使用数组保存结点，很容易就可以做到，这里不再赘述
快慢指针的话，首先先循环一次，判断是否是环形链表，不是的话直接返回null。是的话，则记录下相遇点。然后head开始跑，同时fast指针继续从相遇点跑，则head必然会和fast指针在环形链表交点相遇。

var detectCycle = function(head) {
    
    let slow = fast = head

    while(fast && fast.next){

        slow = slow.next

        fast = fast.next.next

        if(slow == fast) {
        
            while(fast != head){
        
                head = head.next
        
                fast = fast.next
            }

            return head
        }
    }

    return null
};

2019 算法面试相关(leetcode)--数组和链表

猜你喜欢

热点阅读