链表

反转链表

ListNode* ReverseList(ListNode* pHead) {
    if(pHead == NULL) return NULL;
    ListNode* cur = pHead;
    ListNode* pre = NULL;
    ListNode* next = NULL;
    while(cur != NULL){
        next = cur -> next;
        cur -> next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

输入一个链表，输出该链表中倒数第k个结点。

ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
    vector<ListNode*> v;
    while(pListHead!=NULL){
        v.push_back(pListHead);
        pListHead = pListHead->next;
    }
    if(v.size() < k || k < 1) return NULL;
    return v[v.size() - k];  
}

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

ListNode* Merge(ListNode* pHead1, ListNode* pHead2){
       ListNode* p = new ListNode(-1);
       ListNode* root= p;
       while(pHead1 != NULL || pHead2 != NULL){
           if(pHead1 == NULL){
               p->next = pHead2;
               break;
           }
           if(pHead2 == NULL){
               p->next = pHead1;
               break;
           }
           if(pHead1 -> val < pHead2 -> val){
               p->next = pHead1;
               p = p->next;
               pHead1 = pHead1 -> next;
           }else{
               p->next = pHead2;
               p = p-> next;
               pHead2 = pHead2->next;
           }
       }
       return root->next;       
}

输入一个链表，从尾到头打印链表每个节点的值。

vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> v;
        if(head == NULL) return v;
        while(head != NULL){
            v.push_back(head->val);
            head = head->next;
        }
        std::reverse(v.begin(), v.end());
        return v;
}