链表笔试

发表于

###分段交换链表
Swap Nodes in Pairs

Given 1->2->3->4, you should return the list as 2->1->4->3.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        
        if(head==None):
            return head
        
        trav1 = head
        trav2 = head.next
        
        if(trav2==None):
            return head
        
        head = head.next
        
        while(True):
            trav1.next = trav1.next.next
            trav2.next = trav1
            
            if trav1.next == None or trav2.next==None:
                break            
            
            trav2 = trav1.next
            if trav2.next == None:
                break            
           
            trav1.next = trav2.next
            trav1 = trav2
            trav2 = trav2.next
            
        return head

###往右移动k个链表

1
2
3
4
5
6
7
Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

计算链表长度，用k%len，得到实际移动长度，然后用双箭头，标记新的头和新的结尾

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        
        if head == None:
            return None
        
        cur = head
        length = 1
        pos = 0
        table = {}
        # count how many steps we need
        while cur and cur.next:
            cur = cur.next
            length += 1
        steps = k % length
        
        n = 0
        lastk = head
        while n < steps:
            lastk = lastk.next
            n+=1
            
        last = head
        while lastk.next != None:
            lastk = lastk.next
            last = last.next
            
        lastk.next = head
        newhead = last.next
        last.next = None
        return newhead

###链表转换二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """
        tree = []
        while head:
            tree.append(head.val)
            head = head.next
        root = self.constructTree(tree)        
        return root
    
    def constructTree(self, tree):
        if not tree:
            return
        mid = len(tree)/2
        root = TreeNode(tree[mid])
        root.left = self.constructTree(tree[:mid])
        root.right = self.constructTree(tree[mid+1:])
        return root

###深拷贝包含随机指针的链表

第一次遍历使用map存储新的节点，第二次遍历添加随机指针和正常指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Definition for singly-linked list with a random pointer.
# class RandomListNode(object):
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        map = {}
        iterNode = head
        while iterNode:
            map[iterNode] = RandomListNode(iterNode.label)
            iterNode = iterNode.next
        
        iterNode = head
        while iterNode:
            map[iterNode].next = map[iterNode.next] if iterNode.next else None
            map[iterNode].random = map[iterNode.random] if iterNode.random else None
            iterNode = iterNode.next
        return map[head] if head else None