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

2019 iOS面试题大全---全方面剖析面试
2018 iOS面试题---算法相关
1、七种常见的数组排序算法整理(C语言版本)
2、2019 算法面试相关(leetcode)--数组和链表
3、2019 算法面试相关(leetcode)--字符串
4、2019 算法面试相关(leetcode)--栈和队列
5、2019 算法面试相关(leetcode)--优先队列
6、2019 算法面试相关(leetcode)--哈希表
7、2019 算法面试相关(leetcode)--树、二叉树、二叉搜索树
8、2019 算法面试相关(leetcode)--递归与分治
9、2019 算法面试相关(leetcode)--贪心算法
10、2019 算法面试相关(leetcode)--动态规划(Dynamic Programming)
11、2019 算法面试相关(leetcode)--动态规划之背包问题


反转链表
两两交换链表中的节点
环形链表
环形链表 II

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

  • 下面主要针对leetcode上关于链表的一些题目,这里我是使用的JavaScript
function ListNode(val) {
    this.val = val;
    this.next = null;
}

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

示例:

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


  • 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;
};

二 、两两交换链表中的节点
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.
说明:

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。


记录相邻两个结点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
};

三、环形链表
给定一个链表,判断链表中是否有环。

为了表示给定链表中的环,大家使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos-1,则在该链表中没有环。

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:true
说明:链表中有一个环,其尾部连接到第二个节点。

image

示例 2:

输入:head = [1,2], pos = 0
输出:true
说明:链表中有一个环,其尾部连接到第一个节点。

image

示例 3:

输入:head = [1], pos = -1
输出:false
说明:链表中没有环。

image

进阶:

你能用 O(1)(即,常量)内存解决此问题吗?


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

  • 1、比较容易想到的就是利用数组或集合:循环链表,将结点依次保存在集合中,如果下个结点已经在集合中存在,则说明是环形链表。如果循环到最后指向null,则非环形链表。
var hasCycle = function(head) {
    
    let set = new Set()

    while(head){

        if(set.has(head)) return true

        set.add(head)

        head = head.next
    }

    return false
};

但题目有要求让用o(1)空间复杂度解决,但这种方法空间复杂度很明显是o(n),不符合要求

  • 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。

为了表示给定链表中的环,大家使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。
示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:tail connects to node index 1
说明:链表中有一个环,其尾部连接到第二个节点。

image

示例 2:

输入:head = [1,2], pos = 0
输出:tail connects to node index 0
说明:链表中有一个环,其尾部连接到第一个节点。

image

示例 3:

输入:head = [1], pos = -1
输出:no cycle
说明:链表中没有环。

image

说明:不允许修改给定的链表。


题目意思是如果链表是环形链表,就返回交点(链表尾连接到链表中的位置)在该链表中的位置,否则返回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
};

推荐阅读更多精彩内容