本文共 10744 字，大约阅读时间需要 35 分钟。

笔试刷题必备------ 链表

删除链表中的节点

示例 1:

输入: head = [4,5,1,9], node = 5输出: [4,1,9]

解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2:

输入: head = [4,5,1,9], node = 1输出: [4,5,9]

解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明:

链表至少包含两个节点。

链表中所有节点的值都是唯一的。 给定的节点为非末尾节点并且一定是链表中的一个有效节点。 不要从你的函数中返回任何结果。

class ListNode(object):    def __init__(self,x):        self.val = x        self.next = Noneclass Solution(object):    def delete_node(self,head,node):        #找到被删除的前一个节点        p = head        while p.next != None:            if p.next.val == node:                p.next = p.next.next            p = p.next        return headif __name__ == "__main__":    node1 = ListNode(4)    node2 = ListNode(5)    node3 = ListNode(1)    node4 = ListNode(9)    node1.next = node2    node2.next = node3    node3.next = node4    node4.next = None    solu = Solution()    res = solu.delete_node(node1,1)    while res.next != None:        print(res.val)        res = res.next    print(res.val)

环形链表

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

class ListNode(object):    def __init__(self,x):        self.val = x        self.next = Noneclass Solution(object):    def has_cycle(self,head):        if head == None or head.next == None:            return False        fast = head        slow = head        while fast and fast.next:            fast = fast.next.next            slow = slow.next            if slow == fast:                return True        return Falseif __name__ == "__main__":    node1 = ListNode(3)    node2 = ListNode(2)    node3 = ListNode(0)    node4 = ListNode(-4)    node1.next = node2    node2.next = node3    node3.next = node4    node4.next = node2    solu = Solution()    print(solu.has_cycle(node1))

删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

快慢指针：

class ListNode(object):    def __init__(self,x):        self.val = x        self.next = Noneclass Solution(object):    def remove_Nth_from_end(self,head,n):        p = head        fast = slow = p        while n > 0 and fast.next != None:            n -= 1            fast = fast.next        if fast.next == None:            return p.next        while fast != None and fast.next != None:            fast = fast.next            slow = slow.next        slow.next = slow.next.next        return pif __name__ == "__main__":    node1 = ListNode(1)    node2 = ListNode(2)    node3 = ListNode(3)    node4 = ListNode(4)    node5 = ListNode(5)    node6 = ListNode(6)    node1.next = node2    node2.next = node3    node3.next = node4    node4.next = node5    node5.next = node6    node6.next = None    solu = Solution()    res = solu.remove_Nth_from_end(node1,9)    while res.next != None:        print(res.val)        res = res.next    print(res.val)

合并两个有序链表

常规方法（仅使用链表）：

class ListNode(object):    def __init__(self,x):        self.val = x        self.next = Noneclass Solution(object):    def merge_two_list(self,l1,l2):    	if l1 == None:			return l2		if l2 == None:			return l1        head_node = ListNode("head")        p = head_node        p1 = l1        p2 = l2        while p1.next != None and p2.next != None:            if p1.val < p2.val:                p.next = p1                p1 = p1.next            else:                p.next = p2                p2 = p2.next            p = p.next        while p1.next != None:            p.next = p1            p1 = p1.next            p = p.next        while p2.next != None:            p.next = p2            p2 = p2.next            p = p.next        return head_node.nextif __name__ == "__main__":    l11 = ListNode(1)    l12 = ListNode(3)    l13 = ListNode(5)    l14 = ListNode(7)    l15 = ListNode(9)    l21 = ListNode(1)    l22 = ListNode(14)    l23 = ListNode(16)    l24 = ListNode(18)    l25 = ListNode(110)    l11.next = l12    l12.next = l13    l13.next = l14    l14.next = l15    l21.next = l22    l22.next = l23    l23.next = l24    l24.next = l25    solu = Solution()    res = solu.merge_two_list(l11,l21)    while res.next != None:        print(res.val)        res = res.next    print(res.val)

递归方法：

def merge_two_list_recursive(self,l1,l2):        if l1 == None:            return l2        if l2 == None:            return l1        if l1.val < l2.val:            l1.next = self.merge_two_list_recursive(l1.next,l2)            return l1        if l2.val < l1.val:            l2.next = self.merge_two_list_recursive(l1,l2.next)            return l2

反转链表

反转一个单链表。

示例:

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

进阶:

你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

class ListNode(object):    def __init__(self,x):        self.val = x        self.next = Noneclass Solution(object):    def reverse_list(self,head):        if head == None:            return None        pre = None        cur = head        nxt = cur.next        while nxt:            cur.next = pre            pre = cur            cur = nxt            nxt = nxt.next        cur.next = pre        head = cur        return headif __name__ == "__main__":    node1 = ListNode(1)    node2 = ListNode(2)    node3 = ListNode(3)    node4 = ListNode(4)    node5 = ListNode(5)    node1.next = node2    node2.next = node3    node3.next = node4    node4.next = node5    solu = Solution()    res = solu.reverse_list(node1)    while res.next != None:        print(res.val)        res = res.next    print(res.val)

回文链表

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2输出: false

示例 2:

输入: 1->2->2->1输出: true

进阶：

你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

class ListNode(object):    def __init__(self,x):        self.val = x        self.next = Noneclass Solution(object):    def is_palindrome(self,head):        val_list = []        while head.next != None:            val_list.append(head.val)            head = head.next        val_list.append(head.val)        return val_list == val_list[::-1]if __name__ == "__main__":    node1 = ListNode(1)    node2 = ListNode(2)    node3 = ListNode(3)    node4 = ListNode(3)    node5 = ListNode(2)    node6 = ListNode(1)    node1.next = node2    node2.next = node3    node3.next = node4    node4.next = node5    node5.next = node6    solu = Solution()    print(solu.is_palindrome(node1))

两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)

输出：7 -> 0 -> 8 原因：342 + 465 = 807

class ListNode(object):    def __init__(self,x):        self.val = x        self.next = Noneclass Solution(object):    def add_two_numbers(self,l1,l2):        num1_list = []        num2_list = []        num1 = 0        num2 = 0        sum_num = 0        while l1.next != None:            num1_list.append(l1.val)            l1 = l1.next        num1_list.append(l1.val)        while l2.next != None:            num2_list.append(l2.val)            l2 = l2.next        num2_list.append(l2.val)        d1 = 1        for i in range(len(num1_list)-1,-1,-1):            temp = num1_list[i]*d1            num1 += temp            d1*=10        d2 = 1        for i in range(len(num2_list)-1,-1,-1):            temp = num2_list[i]*d2            num2 += temp            d2*=10        sum_num = num1+num2        sum_list = list(str(sum_num))[::-1]        index = 0        for i in range(len(sum_list)):            if sum_list[i] != '0':                index = i                break        sum_list = sum_list[index:]        head = ListNode(int(sum_list[0]))        p = head        for i in range(1,len(sum_list)):            p.next = ListNode(int(sum_list[i]))            p = p.next        return headif __name__ == "__main__":     l11 = ListNode(2)     l12 = ListNode(4)     l13 = ListNode(3)     l14 = ListNode(0)     l15 = ListNode(0)     l21 = ListNode(5)     l22 = ListNode(6)     l23 = ListNode(4)     l24 = ListNode(0)     l25 = ListNode(0)     l11.next = l12     l12.next = l13     l13.next = l14     l14.next = l15     l21.next = l22     l22.next = l23     l23.next = l24     l24.next = l25     solu = Solution()     res = solu.add_two_numbers(l11,l21)     while res.next != None:         print(res.val)         res = res.next     print(res.val)

奇偶链表

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例 1:

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

示例 2:

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

说明:

应当保持奇数节点和偶数节点的相对顺序。

链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

class ListNode(object):	def __init__(self,x):		self.val = x		self.next = Noneclass Solution(object):	def odd_even_list(self,head):		if head == None or head.next == None:			return head 		odd = odd_head = head.next		even = head		while even and even.next and odd and odd.next:			even.next = even.next.next			even = even.next			odd.next = odd.next.next			odd = odd.next		even.next = odd_head		return head

相交链表

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出：Reference of the node with value = 8 输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输出：Reference of the node with value = 2 输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。 输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出：null 输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。 解释：这两个链表不相交，因此返回 null。

class ListNode(object):    def __init__(self,x):        self.val = x        self.next = Noneclass Solution(object):    def get_intersection_node(self,headA,headB):        if headA == None or headB == None:            return None        p,q = headA,headB        countA,countB = 0,0        while p != None:            p = p.next            countA += 1        while q != None:            q = q.next            countB += 1        m,n = headA,headB        if countA > countB:            for i in range(countA-countB):                m = m.next        else:            for i in range(countB-countA):                n = n.next        while m != n:            m = m.next            n = n.next        return mif __name__ == "__main__":    l11 = ListNode(4)    l12 = ListNode(1)    l13 = ListNode(8)    l14 = ListNode(4)    l15 = ListNode(5)    l21 = ListNode(0)    l22 = ListNode(1)    l23 = ListNode(8)    l24 = ListNode(4)    l25 = ListNode(5)    l11.next = l12    l12.next = l13    l13.next = l14    l14.next = l15    l21.next = l22    l22.next = l13    l13.next = l14    l14.next = l15    solu = Solution()    res = solu.get_intersection_node(l11,l21)    print(res.val)

转载地址：http://xluib.baihongyu.com/