《剑指Offer》链表

1基本概念

链表是一种动态数据结构，内存分配不是在创建链表时一次性完成的，而是每添加一个节点分配一次内存。由于没有闲置的内存，链表的空间效率比数组高。

单向链表的节点定义和向末尾添加节点的C++代码如下所示：

struct ListNode{
    int m_nValue;
    ListNode* m_pNext;
};

//add node to linked list

void AddToTail(ListNode** pHead, int value){
    ListNode* pNew = new ListNode();
    pNew -> m_nValue = value;
    pNew -> m_pNext = nullptr;
    
    if(*pHead == nullptr){
        *pHead = pNew;
    }
    else{
        ListNode* pNode = *pHead;
        while(pNode -> m_pNext!=nullptr)
            pNode = pNode ->m_pNext;
        pNode -> m_pNext = pNew;
    }
}

其中AddToTail()函数的第一个参数，pHead是一个指向指针的指针。当我们往一个空链表中插入一个节点时，新插入的节点就是链表的头指针。由于此时会改动头指针，因此必须把pHead参数设为指向指针的指针，否则出了这个函数pHead仍然是一个空指针。

由于链表中的内存不是一次性分配的，因此我们无法保证链表的内存和数组一样是连续的。因此如果想要在链表中找到它的第i个节点，那么我们只能从头节点开始，沿着指向下一个节点的指针遍历链表，它的时间效率为O(n)。而在数组中，我们可以根据下标在O(1)时间内找到第i个元素。

下面是在链表中找到第一个含有某值的节点并删除该节点的代码。

void RemoveNode(ListNode** pHead, int value){
    if(pHead == nullptr || *pHead == nullptr)
        return;
    
    ListNode* pToBeDeleted = nullptr;
    if((*pHead)->m_nValue == value){
        pToBeDeleted = *pHead;
        *pHead = (*pHead) -> m_pNext;
    }
    else{
        ListNode* pNode = *pHead;
        while(pNode -> m_pNext!=nullptr && pNode ->m_pNext->m_nValue!=value)
            pNode = pNode->m_pNext;
        if(pNode_m_pNext!=nullptr&& pNode->m_pNext ->m_nValue == value){
            pToBeDeleted = pNode ->m_pNext;
            pNode->m_pNext = pNode->m_pNext->m_pNext;
        }
    }
    
    if(pToBeDeleted !=nullptr)
    {
        delete pToBeDleted;
        pToBeDeleted = nullptr;
    }
}

2 逆序遍历打印链表

使用栈从头到尾存储链表节点，然后再一个一个打印出来。

//print linked list's data from tail to head 
//using stack
void PrintListReversingly_Iteratively(ListNode* pHead){
    std::stack<ListNode*> nodes;
    
    ListNode* pNode = pHead;
    while(pNode!=nullptr){
        nodes.push(pNode);
        pNode = pNode->m_pNext;
    }
    while(!nodes.empty()){
        pNode = nodes.top();
        printf("%d\t", pNode->m_nValue);
        nodes.pop();
    }
}

考虑到递归本质上就是一个栈结构，于是想到用递归来实现。要实现反过来输出链表，我们每访问到一个节点的时候，先递归输出它后面的节点，再输出该节点自身。这样链表的输出结果就反过来了。

//递归实现逆序打印链表
void PrintListReversingly_Recursively(ListNode* pHead){
    if(pHead!=nullptr){
        if(pHead -> m_pNext!=nullptr){
            PrintListReversingly_Recursively(pHead->m_pNext);
        }
        printf("%d\t", pHead -> m_nValue);
    }
}

上面的基于递归的代码看起来很简洁，但有一个问题：当链表非常长的时候，就会导致函数调用的层次很深，从而有可能导致函数调用栈溢出。显然用第一个基于循环的代码鲁棒性更好。

逆序打印链表的Python实现（栈的方法）：
27 ms， 6364K

class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    # using a stack
    def printListFromTailToHead(self,listNode):
        ans = []
        if listNode == None:
            return ans
        else:
            thenode  = listNode
            while thenode.next !=None:
                ans.append(thenode.val)
                thenode = thenode.next
            ans.append(thenode.val)
        return ans[::-1]

递归的方法：
26 ms, 5712K

    def printListFromTailToHead(self, listNode):
        # write code here
        if listNode  == None:
            return []
        else:
            return self.printListFromTailToHead(listNode.next) + [listNode.val]

其实Python的递归函数很容易写，要掌握规律。

3 Python实现链表工具类

# 节点
class ListNode:
    def __init__(self,x):
        self.val = x
        self.next = None
# 链表
class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def is_empty(self):
        return self.head is None

    def append(self,data):
        lnode = ListNode(data)
        if self.head is None:
            self.head = lnode
            self.tail = lnode
        else:
            self.tail.next = lnode
            self.tail = lnode

    def printlink(self):
        if self.head is None:
            print('None')
        else:
            thenode = self.head
            while thenode.next !=None:
                print(thenode.val,end='\t')
                thenode = thenode.next
            if thenode.val !=None:
                print(thenode.val)