Cracking the Coding Interview-2.2

第六版Cracking the Coding Interview题目2.2，题目如下：

Return Kth to Last: Implement an algorithm to find the kth to last element of a singly linked list.

题目要求返回单链表倒数第k个元素，如果使用Python的list直接list[-k]即可。但这样失去了这道题目的意义，所以自己先来写一个简单的单链表。除此之外，如果知道链表的长度，则链表长度减k个即为倒数第k个。总结起来如下：

class Node():

    def __init__(self, item):
        self._item = item
        self._next = None

    def getItem(self):
        return self._item

    def getNext(self):
        return self._next

    def setItem(self, newitem):
        self._item = newitem

    def setNext(self, newnext):
        self._next = newnext


class SingleLinkedList():

    def __init__(self, items=None):
        self._head = None
        self._size = 0
        if items is not None:
            for item in items[::-1]:
                self.add(item)

    def getHead(self):
        return self._head

    def getSize(self):
        return self._size

    def isEmpty(self):
        return self.getSize() == 0

    def add(self, item):  # 向头部添加
        node = Node(item)
        node.setNext(self._head)
        self._head = node
        self._size += 1

    def getNodeAt(self, index):
        if index < 0:
            index = self.getSize() + index
        if not 0 <= index < self.getSize():
            raise IndexError('list index out of range')
        current = self.getHead()
        for i in xrange(index):
            current = current.getNext()
        return current

    def removeNodeAt(self,index):
        if self.isEmpty():
            rasie RuntimeError('remove node on an empty list')
        if index == 0:
            node = self.getHead()
            self._head = node.getNext()
            del node
        else:
            prev = self.getNodeAt(index - 1)
            node = prev.getNext()
            next = node.getNext()
            prev.setNext(next)
            del node
        self._size -= 1

    def getItemAt(self, index):
        return self.getNodeAt(index).getItem()

    def __str__(self):
        stringBuilder=[]
        current=self.getHead()
        while current is not None:
            stringBuilder.append(str(current.getItem()))
            current=current.getNext()
        return '->'.join(stringBuilder)

上面实现了简单的单链表，可以直接从list构造单链表，更多的方法会在以后需要的时候会再添加上去。getItemAt会返回特定位置的元素，如果index为负数则为从后往前数。

但如果无法知道链表的长度怎么办？最简单的是先历遍一次链表得出链表的长度，第二次再去查找。但是如果在循环链表时使用两个指针，那么便可以省去第二遍去寻找。

def kthToLast(ll, k):
    if ll.isEmpty():
        return None
    p1 = ll.getHead()
    p2 = p1

    # 将p1向后移动k个节点
    for i in xrange(k):
        if p1.getNext() is None: # 超出边界
            return None
        p1 = p1.getNext()

    # 同时移动p1和p2
    while p1.getNext() is not None:
        p1 = p1.getNext()
        p2 = p2.getNext()
    return p2.getItem()

这道问题主要考察单链表的基本知识，难度较小。比较有意思的是，这个问题也可以通过递归来完成，具体如下：

def kthToLast(ll, k):
    def kthToLastRecursive(node,k):
        if node is None:
            return -1, None
        index, item = kthToLastRecursive(node.getNext(), k)
        index += 1
        if index == k:
            return index, node.getItem()
        return index, item
    return kthToLastRecursive(ll.getHead(),k)[1]

在手机上阅读或分享本文请扫描以下二维码：

Cracking the Coding Interview-2.2

Comments