链表

数据结构

题目链接:http://blog.csdn.net/u011412619/article/details/44541143

链表的创建

通常head就是第一个具有value的节点，而tail->next指向一个NULL节点。
链表的插入有头插法和尾插法两种实现方式，通常取决于题目所要求的元素顺序。
头插法:
初始head = NULL
new -> next = head;
head = new;
尾插法:
初始tail = node1
tail->next = new
tail = new

求单链表中结点的个数

int GetListLength(ListNode * pHead)  
{  
    if(pHead == NULL)  
        return 0;  
    unsigned int nLength = 0;  
    ListNode * pCurrent = pHead;  
    while(pCurrent != NULL)  
    {  
        nLength++;  
        pCurrent = pCurrent -> Next;  
    }  
    return nLength;  
}

反转链表

ListNode * ReverseList(ListNode * pHead)  
{  
    if(pHead == NULL || pHead->Next == NULL)    
        return pHead;
    ListNode * pReversedHead = NULL; 
    ListNode * pCurrent = pHead;  
    while(pCurrent != NULL)  
    {  
        ListNode * pTemp = pCurrent; //取下一个节点
        pCurrent = pCurrent->Next; 
        pTemp->Next = pReversedHead; //头插法得到的链表正好是逆序
        pReversedHead = pTemp;  
    }
    return pReversedHead;  
}

查找单链表中的倒数第K个结点（k > 0）

ListNode * RGetKthNode(ListNode * pHead, int k) //函数名前面的R代表反向  
{  
    if(k == 0 || pHead == NULL)
        return NULL;  
    ListNode * pAhead = pHead;  
    ListNode * pBehind = pHead;  
    while(k > 1 && pAhead != NULL) //前面的指针先走到正向第k个结点
    {  
        pAhead = pAhead -> Next;  
        k--;
    }
    if(k > 1 || pAhead == NULL)     // 结点个数小于k，返回NULL  
        return NULL;  
    while(pAhead -> Next != NULL)  //前后两个指针一起向前走，直到前面的指针指向最后一个结点  
    {  
        pBehind = pBehind -> Next;  
        pAhead = pAhead -> Next;  
    }
    return pBehind;  // 后面的指针所指结点就是倒数第k个结点  
}

查找单链表的中间结点

ListNode * GetMiddleNode(ListNode * pHead)  
{  
    if(pHead == NULL || pHead -> Next == NULL) 
        return pHead;  
    ListNode * pAhead = pHead;  
    ListNode * pBehind = pHead;  
    while(pAhead->Next != NULL) //前面指针每次走两步，直到指向最后一个结点，后面指针每次走一步  
    {  
        pAhead = pAhead->Next;  
        pBehind = pBehind->Next;  
        if(pAhead->Next != NULL)  
            pAhead = pAhead->Next;  
    }
    return pBehind; // 后面的指针所指结点即为中间结点  
}  

从尾到头打印单链表

//使用栈
void RPrintList(ListNode * pHead)  
{  
    std::stack<ListNode *> s;  
    ListNode * pNode = pHead;  
    while(pNode != NULL)  
    {  
        s.push(pNode);  
        pNode = pNode->Next;  
    }
    while(!s.empty())  
    {  
        pNode = s.top();  
        printf("%d\t", pNode->value);  
        s.pop();  
    }
}
//使用系统栈，递归函数
// 从尾到头打印链表，使用递归  
void RPrintList(ListNode * pHead)  
{  
    if(pHead == NULL)  
    {  
        return;  
    }
    else  
    {  
        RPrintList(pHead->Next);  
        printf("%d\t", pHead->value);  
    }
}

合并两个有序列表

ListNode * MergeSortedList(ListNode * pHead1, ListNode * pHead2)  
{  
    if(pHead1 == NULL)
        return pHead2;  
    if(pHead2 == NULL)  
        return pHead1;  
    ListNode * pHeadMerged = NULL;  
    if(pHead1->m_nKey < pHead2->m_nKey)  
    {  
        pHeadMerged = pHead1;  
        pHeadMerged->Next = NULL;  
        pHead1 = pHead1->Next;  
    }  
    else  
    {  
        pHeadMerged = pHead2;  
        pHeadMerged->Next = NULL;  
        pHead2 = pHead2->Next;  
    }  
    ListNode * pTemp = pHeadMerged;//以上首先初始化了头部，因为要使用尾插法构造链表，不能使用头部插入法
    while(pHead1 != NULL && pHead2 != NULL)  
    {  
        if(pHead1->m_nKey < pHead2->m_nKey)  
        {  
            pTemp->Next = pHead1;  
            pHead1 = pHead1->Next;  
            pTemp = pTemp->Next;  
            pTemp->Next = NULL;  
        }  
        else  
        {  
            pTemp->Next = pHead2;  
            pHead2 = pHead2->Next;  
            pTemp = pTemp->Next;  
            pTemp->Next = NULL;  
        }
    }
    if(pHead1 != NULL)  
        pTemp->Next = pHead1;  
    else if(pHead2 != NULL)  
        pTemp->Next = pHead2;  
    return pHeadMerged;  
}
//递归版本
ListNode * MergeSortedList(ListNode * pHead1, ListNode * pHead2)  
{  
    if(pHead1 == NULL)  
        return pHead2;  
    if(pHead2 == NULL)  
        return pHead1;  
    ListNode * pHeadMerged = NULL;  
    if(pHead1->m_nKey < pHead2->m_nKey)  
    {  
        pHeadMerged = pHead1; 
        pHeadMerged->Next = MergeSortedList(pHead1->Next, pHead2);
    }
    else  
    {
        pHeadMerged = pHead2;  
        pHeadMerged->Next = MergeSortedList(pHead1, pHead2->Next);
    }  
    return pHeadMerged;  
}

扩展延伸---合并k个链表
思路:
1. 用最小堆去维护，取走一个，再把该元素下一个放入最小堆，使用时直接调用STL的priority_queue即可
2. 分治法 Divide and Conquer Approach，不停的两两合并

ListNode *mergeKLists(vector<ListNode *> &lists) {
        if (lists.size() == 0) return NULL;
        int n = lists.size();
        while (n > 1) {
            int k = (n + 1) / 2;
            for (int i = 0; i < n / 2; ++i) {
                lists[i] = mergeTwoLists(lists[i], lists[i + k]);
            }
            n = k;
        }
        return lists[0];
    } //类似于非递归实现的归并排序

判断一个单链表中是否有环

bool HasCircle(ListNode * pHead)  
{  
    ListNode * pFast = pHead; // 快指针每次前进两步  
    ListNode * pSlow = pHead; // 慢指针每次前进一步  
    while(pFast != NULL && pFast->Next != NULL)  
    {  
        pFast = pFast->Next->Next;  
        pSlow = pSlow->Next;  
        if(pSlow == pFast) // 相遇，存在环  
            return true;  
    }
    return false;  
}
//如果跑的快的走了两圈的话，那么一定跑的慢的一定只走了一圈，距离差两倍

求进入环的第一个节点

首先判断是否存在环，若不存在结束。在环中的一个节点处断开，这样就形成了两个相交的单链表，求进入环中的第一个节点也就转换成了求两个单链表相交的第一个节点。
见leetcode Linked List Cycle，方法二: 通过证明，得到了起始点的更简单的思路。首先得到环的长度，然后设置两个指针一个前一个后即可~ 长度(在相遇点，让一个指针再跑一圈，下次相遇时走过的长度即为环的长度)
http://www.cnblogs.com/x1957/p/3406448.html
注意这是一个链表不是两个。

ListNode* GetFirstNodeInCircle(ListNode * pHead)  
{  
    if(pHead == NULL || pHead->Next == NULL)  
        return NULL;  
    ListNode * pFast = pHead;  
    ListNode * pSlow = pHead;  
    while(pFast != NULL && pFast->Next != NULL) //判断是否有环
    {  
        pSlow = pSlow->Next;  
        pFast = pFast->Next->Next;  
        if(pSlow == pFast)  
            break;  
    }  
    if(pFast == NULL || pFast->Next == NULL)  
        return NULL;
    // 将环中的此节点作为假设的尾节点，将它变成两个单链表相交问题     //这里最好画个图看一下两个链表的形状是如何的
    ListNode * pAssumedTail = pSlow;
    ListNode * pHead1 = pHead;
    ListNode * pHead2 = pAssumedTail->Next;
    ListNode * pNode1, * pNode2;  
    int len1 = 1;  
    ListNode * pNode1 = pHead1;  
    while(pNode1 != pAssumedTail)  
    {  
        pNode1 = pNode1->Next;  
        len1++;  
    }  
    int len2 = 1;  
    ListNode * pNode2 = pHead2;  
    while(pNode2 != pAssumedTail) 
    {  
        pNode2 = pNode2->Next;  
        len2++;  
    }  
    pNode1 = pHead1;  
    pNode2 = pHead2; 
    if(len1 > len2)  
    {  
        int k = len1 - len2;  
        while(k--)  
            pNode1 = pNode1->Next;  
    }  
    else  
    {  
        int k = len2 - len1;  
        while(k--)  
            pNode2 = pNode2->Next;  
    }  
    while(pNode1 != pNode2)  
    {  
        pNode1 = pNode1->Next;  
        pNode2 = pNode2->Next;  
    }  
    return pNode1;  
} 

判断两个单链表是否相交

两个链表相交意味着他们有着一段公共的串。

bool IsIntersected(ListNode * pHead1, ListNode * pHead2)  
{  
    if(pHead1 == NULL || pHead2 == NULL)  
        return false;
    ListNode * pTail1 = pHead1;  
    while(pTail1->Next != NULL)  
        pTail1 = pTail1->Next;
    ListNode * pTail2 = pHead2;  
    while(pTail2->Next != NULL)  
        pTail2 = pTail2->Next;  
    return pTail1 == pTail2;  
}

求两个单链表相交的第一个节点

对第一个链表遍历，计算长度len1，同时保存最后一个节点的地址。
对第二个链表遍历，计算长度len2，同时检查最后一个节点是否和第一个链表的最后一个节点相同，若不相同，不相交，结束。
两个链表均从头节点开始，假设len1大于len2，那么将第一个链表先遍历len1-len2个节点，此时两个链表当前节点到第一个相交节点的距离就相等了，然后一起向后遍历，直到两个节点的地址相同。

ListNode* GetFirstCommonNode(ListNode * pHead1, ListNode * pHead2)  
{  
    if(pHead1 == NULL || pHead2 == NULL)  
        return NULL;  
    int len1 = 1;  
    ListNode * pTail1 = pHead1;  
    while(pTail1->Next != NULL)  
    {  
        pTail1 = pTail1->Next;  
        len1++;  
    }  
    int len2 = 1;  
    ListNode * pTail2 = pHead2;  
    while(pTail2->Next != NULL)  
    {  
        pTail2 = pTail2->Next;  
        len2++;  
    }  
    if(pTail1 != pTail2) // 不相交直接返回NULL  
        return NULL;  
    ListNode * pNode1 = pHead1;  
    ListNode * pNode2 = pHead2;  
        // 先对齐两个链表的当前结点，使之到尾节点的距离相等  
    if(len1 > len2)  
    {  
        int k = len1 - len2;  
        while(k--)  
            pNode1 = pNode1->Next;  
    }  
    else  
    {  
        int k = len2 - len1;  
        while(k--)  
            pNode2 = pNode2->Next;  
    }  
    while(pNode1 != pNode2)  
    {  
        pNode1 = pNode1->Next;  
        pNode2 = pNode2->Next;  
    }  
        return pNode1;  
}  

O(1)时间复杂度删除节点

我们可以把该节点的下一个节点的数据复制到该节点，然后删除下一个节点即可。要注意最后一个节点的情况,此时只能按照常规方法删除(记录前一个节点)。

void Delete(ListNode * pHead, ListNode * pToBeDeleted)  
{  
    if(pToBeDeleted == NULL)  
        return;  
    if(pToBeDeleted->Next != NULL)  
    {  
        pToBeDeleted->m_nKey = pToBeDeleted->Next->m_nKey;  
        ListNode * temp = pToBeDeleted->Next;  
        pToBeDeleted->Next = pToBeDeleted->Next->Next;  
        delete temp;  
    }  
    else // 要删除的是最后一个节点  
    {  
        if(pHead == pToBeDeleted) // 链表中只有一个节点的情况  
        {  
            pHead = NULL; 
            delete pToBeDeleted;
        }  
        else  
        {  
            ListNode * pNode = pHead;  
            while(pNode->Next != pToBeDeleted) //找到前一个节点
                pNode = pNode->Next;
            pNode->Next = NULL;  
            delete pToBeDeleted; 
        }     
    }  
}

逆转[m,n]区间内的链表

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct Listnode{
    int val;
    Listnode* next;
    Listnode(int x): val(x),next(NULL){}
};
Listnode* RerveseList(Listnode* head, int m, int n) {
    if (head == NULL) return NULL;
    Listnode * prev = head;
    for (int i = 0; i < m - 1; ++i) {
        prev = prev -> next;
    }
    Listnode * cur = prev -> next;
    Listnode * phead = NULL;
    for (int i = m; i <= n; ++i) {
        Listnode * temp = cur;
        cur = cur -> next;
        temp -> next = phead;
        phead = temp;
    }
    prev -> next -> next = cur;
    prev -> next = phead;
    return head;
}
void print(Listnode* head) {
    Listnode* phead;
    while (phead != NULL) {
        cout << phead -> val << endl;
        phead = phead -> next;
    }
    return;
}
int main() {
    Listnode * head = NULL;
    for (int i = 0; i < 5; ++i) {
        Listnode * temp = new Listnode(i);
        temp -> next = head;
        head = temp;
    }
    head = RerveseList(head, 1, 3);
    print(head);
    return 0;
}

链表与其他数据结构的结合

https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/description/
感觉是遍历过程中再用个stack保存一下遍历中断的节点？

https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/description/
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/
https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/discuss/162900/4-progressively-better-clean-concise-c++-solutions.-O(n)-time-O(logn)-space.-With-descriptions