面试问题整理

恍惚如昨日，自己也面试很多次，经常给别人说一些面试鬼论，本章节中主要介绍链表的一些常用的面试题，希望对大家有用。

一张图

首先看一张图，整理的很多常见的数据结构的复杂度，比较全。

链表

如下定义列表的结构定义。

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

找到倒数第k个节点

class Solution(object):
    def find_kth_to_tail(self,head, k):
        start = head
        from_node = head
        to_node = head
        while k > 0:
            to_node = to_node.next
            k -= 1
        while to_node:
            from_node = from_node.next
            to_node = to_node.next
        return from_node.val

这是一道典型的快慢指针的问题，对于要解决的问题，首先要打破常规，没人规定一个链表里只有一个指针能够遍历。

添加链表中的节点

class Solution(object):
    def add_link_node(self, head, idx, val):
        start = head
        while idx > 0:
            head = head.next
            idx -= 1
        new_node = ListNode(val, None)
        head_next = head.next
        head.next = new_node
        new_node.next =  head_next
        return start

如上面的代码所示，通过idx的自减找到相应的位置，然后将new_node插入到链表中。

删除链表中的节点

class Solution(object):
    def delete_link_node(self, head, idx):
        start = head
        while idx > 1:
            head = head.next
            idx -= 1
        head_next = head.next
        head.next = head_next.next
        del head_next
        return start

倒置单链表

class Solution(object):
    def reverse_link(self, head):
        reverse_node = None
        pre_node = None
        while head:
            head_next = head.next
            if head_next is None:
                reverse_node = head
            head.next = pre_node
            pre_node = head
            head = head_next
        return reverse_node

合并有序单链表

题目描述：
有两个有序单链表list1,list2.目标是将两个链表合并成一个有序链表

class Solution(object):
    def merge_links(self, list1, list2):
        phead = ListNode(-1)
        res = phead
        while list1 or list2:
            if list1 is None:
                res.next = list2
                break
            elif list2 is None:
                res.next = list1
                break
            if list1.val <= list2.val:
                res.next = ListNode(list1.val)
                list1 = list1.next
            else:
                res.next = ListNode(list2.val)
                list2 = list2.next
            res = res.next
        return phead.next

两两交换链表的相邻两个节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

class Solution(object):
    def swap_links(self, head):
        hd = head
        while hd:
            val1 = hd.val
            if hd.next is not None:
                val2 = hd.next.val
                hd.val = val2
                hd.next.val = val1
                hd = hd.next
                hd = hd.next
            else:
                hd = hd.next
        return head

旋转链表

这个问题是一个不同类型的问题，非快慢指针问题，问题描述如下。

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]
按照如下方式旋转，其中k可以大于n，进行多轮旋转。

class Solution(object):
    def rotateRight(self, head, k):
        n = 0
        tmp_head = head
        if head is None or k == 0:
            return head
        while head.next:
            head = head.next
            n += 1
        n += 1
        head.next = tmp_head # 变成循环链表
        head = head.next
        k = k % n
        for i in range(n - k):
            head = head.next
        hd = head
        res = head
        while n > 1:
            hd = hd.next
            n -= 1
        hd.next = None
        return res

如代码所示，将原来的单链表变成循环链表，然后在循环链表进行进行翻转会发现十分容易。打破大家对单链表的固有思路的问题，希望对你有帮助。

判断链表是否有环

判断类似如下链表是否有环的问题。

class Solution(object):
    def hasCycle(self, head):
        faster = head
        slower = head
        if head is None:
            return False
        while head.next:
            if faster.next is None:
                return False
            faster = faster.next
            slower = slower.next
            if faster.next is None:
                return False
            faster = faster.next
            if faster == slower:
                return True
        return False