leetcode-linklist

输出单链表倒数第k个节点

// 双指针法

ListNode* findKthTail(ListNode *pHead, int K){
    if (NULL == pHead || K == 0)
        return NULL;
    //p1，p2均指向头节点
    ListNode *p1 = pHead;
    ListNode *p2 = pHead;
    //p1先出发，前进K个节点
    for (int i = 0; i < K; i++) {
        if (p1)//防止k大于链表节点的个数
            p1 = p1->_next;
        else
            return NULL;
    }

    while (p1)//如果p1没有到达链表结尾，则p1，p2继续遍历
    {
        p1 = p1->_next;
        p2 = p2->_next;
    }
    return p2;//当p1到达末尾时，p2正好指向倒数第K个节点
}

链表中存在环的问题

bool isExistLoop(ListNode* pHead)  {  
    ListNode* fast;//慢指针，每次前进一个节点
    ListNode* slow;//快指针，每次前进2个节点 
    slow = fast = pHead ;  //两个指针均指向链表头节点
    //当没有到达链表结尾，则继续前进
    while (slow != NULL && fast -> next != NULL)  {  
        slow = slow -> next ; //慢指针前进一个节点
        fast = fast -> next -> next ; //快指针前进两个节点
        if (slow == fast)  //若两个指针相遇，且均不为NULL则存在环
            return true ;  
    }  
    //到达末尾仍然没有相遇，则不存在环
    return false ;  
}  

// 快慢指针 

//找到环中的相遇节点
ListNode* getMeetingNode(ListNode* pHead) // 假设为带头节点的单链表{

    ListNode* fast;//慢指针，每次前进一个节点
    ListNode* slow;//快指针，每次前进2个节点 
    slow = fast = pHead ;  //两个指针均指向链表头节点
    //当没有到达链表结尾，则继续前进
    while (slow != NULL && fast -> next != NULL){  
        slow = slow -> next ; //慢指针前进一个节点
        fast = fast -> next -> next ; //快指针前进两个节点
        if (slow == fast)  //若两个指针相遇，且均不为NULL则存在环
            return slow;  
    }  

    //到达末尾仍然没有相遇，则不存在环
    return NULL ;
}
//找出环的入口节点
ListNode* getEntryNodeOfLoop(ListNode* pHead){
    ListNode* meetingNode = getMeetingNode(pHead); // 先找出环中的相遇节点
    if (meetingNode == NULL)
        return NULL;
    ListNode* p1 = meetingNode;
    ListNode* p2 = pHead;
    while (p1 != p2) // p1和p2以相同的速度向前移动，当p2指向环的入口节点时，p1已经围绕着环走了n圈又回到了入口节点。
    {
        p1 = p1->next;
        p2 = p2->next;
    }
    //返回入口节点
    return p1;
}

// 计算环的长度

int getLoopLength(ListNode* head){
    ListNode* slow = head;
    ListNode* fast = head;
    while ( fast && fast->next ){
        slow = slow->next;
        fast = fast->next->next;
        if ( slow == fast )//第一次相遇
            break;
    }
    //slow与fast继续前进
    slow = slow->next;
    fast = fast->next->next;
    int length = 1;       //环长度
    while ( fast != slow )//再次相遇
    {
        slow = slow->next;
        fast = fast->next->next;
        length ++;        //累加
    }
    //当slow与fast再次相遇，得到环长度
    return length;
}

使用链表实现大数相加

ListNode* numberAddAsList(ListNode* l1, ListNode* l2) {
        ListNode *ret = l1, *pre = l1;
        int up = 0;
        while (l1 != NULL && l2 != NULL) {
            //数值相加
            l1->val = l1->val + l2->val + up;
            //计算是否有进位
            up = l1->val / 10;
            //保留计算结果的个位
            l1->val %= 10;
            //记录当前节点位置
            pre = l1;
            //同时向后移位
            l1 = l1->next;
            l2 = l2->next;
        }
        //若l1到达末尾，说明l1长度小于l2
        if (l1 == NULL)
            //pre->next指向l2的当前位置
            pre->next = l2;
        //l1指针指向l2节点当前位置
        l1 = pre->next;
        //继续计算剩余节点
        while (l1 != NULL) {
            l1->val = l1->val + up;
            up = l1->val / 10;
            l1->val %= 10;
            pre = l1;
            l1 = l1->next;
        }

        //最高位计算有进位，则新建一个节点保留最高位
        if (up != 0) {
            ListNode *tmp = new ListNode(up);
            pre->next = tmp;
        }
        //返回计算结果链表
        return ret;
}

有序链表合并

ListNode* mergeTwoOrderedLists(ListNode* pHead1, ListNode* pHead2){
    ListNode* newHead = NULL;
    if (NULL == pHead1){
        return pHead2;
    }else if(NULL ==pHead2){
        return pHead2;
    }else{
        if (pHead1->data < pHead2->data){
            newHead = pHead1;
            newHead->next = mergeTwoOrderedLists(pHead1->next, pHead2);
        }else{
            newHead = pHead2;
            newHead->next = mergeTwoOrderedLists(pHead1, pHead2->next);
         }
        return newHead;
    }   
}

删除链表中节点 要求时间复杂度为1

void deleteNode(ListNode **pHead, ListNode* pDelNode) {
        if(pDelNode == NULL)
            return;
        if(pDelNode->next != NULL){
            ListNode *pNext = pDelNode->next;
            //下一个节点值赋给待删除节点
            pDelNode->val   =  pNext->val;
            //待删除节点指针指后面第二个节点
            pDelNode->next  = pNext->next;
            //删除待删除节点的下一个节点
            delete pNext;
            pNext = NULL;
        }else if(*pHead == pDelNode)//删除的节点是头节点
         {
            delete pDelNode;
            pDelNode= NULL;
            *pHead = NULL;
        } else//删除的是尾节点
        {
            ListNode *pNode = *pHead;
            while(pNode->next != pDelNode) {
                pNode = pNode->next;
            }
            pNode->next = NULL;
            delete pDelNode;
            pDelNode= NULL;
        }
    }

从尾到头打印链表

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> value;
        ListNode *p=NULL;
        p=head;
        stack<int> stk;
        while(p!=NULL){
            stk.push(p->val);
            p=p->next;
        }
        while(!stk.empty()){
            value.push_back(stk.top());
            stk.pop();
        }
        return value;
    }
};


class Solution {
public:
    vector<int> value;
    vector<int> printListFromTailToHead(ListNode* head) {
        ListNode *p=NULL;
        p=head;
        if(p!=NULL){
            if(p->next!=NULL){
                printListFromTailToHead(p->next);
            }
            value.push_back(p->val);
        }
        return value;
    }
};

反转链表

// 迭代

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = NULL;
        ListNode* cur = head;
        while(cur != NULL){
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};


//递归

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 递归终止条件
        if(head == NULL || head->next == NULL)
            return head;

        ListNode* rhead = reverseList(head->next);
        // head->next此刻指向head后面的链表的尾节点
        // head->next->next = head把head节点放在了尾部
        head->next->next = head;
        head->next = NULL;
        return rhead;
    }
};