单链表中K节点逆序

思路

超级大杂烩,左程云出的题的风格。

K节点逆序+ K节点检测 + 链表链接

代码

# include <bits/stdc++.h>
using namespace std;

struct list_node{
    int val;
    struct list_node * next;
};

list_node * input_list()
{
    int val, n;
    scanf("%d", &n);
    list_node * phead = new list_node();
    list_node * cur_pnode = phead;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &val);
        if (i == 1) {
            cur_pnode->val = val;
            cur_pnode->next = NULL;
        }
        else {
            list_node * new_pnode = new list_node();
            new_pnode->val = val;
            new_pnode->next = NULL;
            cur_pnode->next = new_pnode;
            cur_pnode = new_pnode;
        }
    }
    return phead;
}


list_node * reverse_knode(list_node * head1, int K)
{
    list_node whead = {0, head1};
    list_node *before, *pre, *p, *next; // pre, p, next 单单在K个节点逆序起作用; bofore指向逆序链表的前一个节点
    p = head1;
    before = &whead;
    
    while(p) {
        int k = 0;
       list_node *now = before;
        while(k < K){
            k++;
            if (now) now = now->next;
        
        }
        if(now == nullptr) break;
        
        k = 0;
        pre = nullptr;
        list_node *kend = before->next;
        while(k < K) {
            k++;    
            next = p->next;
            p->next = pre;
            pre = p;
            p = next;
            if(next) next = next->next;
        }
        before->next = pre;
        kend->next = p;
        
        before = kend;
        
    }
    return whead.next;

}

void print_list(list_node * head)
{
    while (head != NULL) {
        printf("%d ", head->val);
        head = head->next;
    }
    puts("");
}

int main ()
{
    list_node * head = input_list();
    int K;
    scanf("%d", &K);
    list_node * new_head = reverse_knode(head, K);
    print_list(new_head);
    return 0;
}

约瑟夫问题

思路:

实际上是一个非常巧妙的数学问题。

从结果上来看, 如果只剩最后一个人(最后的幸存者),那么被杀掉一定是它。那么它的当前号码为1,问其原坐标?思考一下新旧人列的下标关系:

Old(k+1) : 
1 2 3 4 5 6 7 --- k + 1 
New(k)
4 5 6    m -1 (s) 1 2 3 

可能的一种形式,其中s是old被杀掉的人的下标。 且s = (m - 1 )% (k + 1) + 1

但不难发现有: old = (new + s - 1) % (k + 1) + 1

综上有逆推式: old =(new + m - 1) % (k + 1) + 1

Read more

面试题 链表相关

所有关于链表的题目都会总结在这里。假设这些题目的链表的头结点都是带有效值的

定义链表

struct ListNode{
    int Value;
    ListNode* pNext;
};

尾插入节点

注意第一个参数是指针的指针,因为有可能需要修改第一个链表节点。

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

删除第一个对应值的链表

viod RemoveNode(ListNode** pHead, int value){
    if(pHead == nullptr || *pHead == nullptr) return;
    ListNode *pToDeleted = nullptr;
    if((*pHead)->value == value){
        pToDeleted = *pHead;
        *pHead = (*pHead)->pNext;
    }else{
        ListNode *pNode = *pHead;
        //pNode指向检查节点的前一个节点
        while((*pNode)->pNext != null && (*pNode)->pNext->value != value){
            pNode = pNode->pNext;
        }
        if((*pNode)->pNext != null && (*pNode)->pNext->value == value){
			pToDeleted = (*pNode)->pNext;
        }
    }
	if(pToDeleted != nullptr){
        delte pToDelted;
        pToDelted = nullptr; //释放内存后,即使是不需要使用的指针,也要做好清除工作,不然不容易维护            
    }
	
}

pToDeleted = *pNode->pNext;上面遍历链表中代码不应该用pToDeleted来记录链表值,否然容易出现代码指针值意义混乱,造成不该删的指针却删掉了。

面试题6 从尾到头打印链表

假如对空间复杂度在O(N)O(N)之上,那么可以使用栈或者递归。

栈代码如下

void PrintListReversingly_Iteratively(ListNode* pHead){
    //使用指针类型的STACK更省内存?
    std::stack<ListNode*> nodes;
    ListNode* pNode = pHead;
    while(pNode != nullptr){
        nodes.push(pNode);
        pNode = pNode->pNext;
    }
    while(!nodes.empty()){
        pNode = nodes.top();
        printf("%d\n", pNode->value);
        nodes.pop();
    }   
}

归代码

void PrintListReversingly_Recursively(ListNode* pHead){
    if(pHead == nullptr) return;
    PrintListReversingly_Recursively(pHead->pNext);
    printf("%d\n", pHead->pNext);
    
}

面试18:删除一个链表节点

题面:

给定一个单向链表的头结点指针和一个指向待删除的节点的指针,要求用O(N)O(N)时间删除节点。

思路:

教科书上的链表删除都是遍历得到上一个待删除的节点的指针,时间复杂度O(N)O(N)。显然不行,也可以直接把待删除的节点K的下一个节点J的内容复制到K上,再删除J,就可以快速删除。考虑边界上,如果没有下一个节点则需要从头遍历;如果只有一个头结点且删除的是头结点,那么只能把头结点置nullptr

其时间复杂度为(n−1)∗O(1)+O(N)(n−1)∗O(1)+O(N)。

代码:

void DeleteNode(ListNode **pHead, ListNode *pToBeDeleted){
    if(pHead == nullptr || (*phead) == nullptr || (*pToBeDeleted) == nullptr ) return;
    ListNode *pFree = nullptr;
    
    if(pToBeDeleted->pNext){
        pFree = ToBeDeleted->pNext;
        pToBeDeleted->value = pToBeDeleted->pNext->value;   
        pToBeDeleted->pNext = pToBeDeleted->pNext->pNext;   
        
    }
    //删除节点无后继节点,且是头结点
    else if( *pHead == pToBeDeleted){
		pFree = *pHead;
        *pHead = nullptr;
    }
    // 链表中多个节点,且删除节点在末尾
    else{
		ListNode *pCur = *pHead
        for(; pCur->pNext->pNext != nullptr; pCur = pCur->pNext);
        pFree = pCur->pNext;
        pCur->pNext = nullptr;
    }
    Delete pFree;
}

错误点:

  • the properiry of “*” > the properity of “==”
  • 链表插入和删除后没有设置指针

注意点:

这个函数假设了待删除的节点一定在链表中;

头结点可能删除掉,所以设置了头结点为指针的指针。

面18(题目二):删除重复值的链表节点

题面:

删除一条已排序的链表中的所有的其值重复出现的节点。

思路:

在上面学习的基础上,连续删除就行,应该是比较简单的。

代码:

void DeleteDuplication(ListNode **pHead){
    if(pHead == nullptr || *pHead == nullptr) return;
    
    ListNode *pCur = *pHead, *pPre = nullptr, *pFree = nullptr;
    //定义一个头结点,避免不同情况的删除
    ListNode *pKid = new ListNode();
    pKid->pNext = *pHead;
    pPre = pKid;
    
    while(pCur != nullptr){
		int value = pCur->value,  isDuplication = 0;
        //删除后面的重复节点
        while(pCur->pNext && pCur->pNext->value == value){
            pFree = pCur->pNext;
            pCur->pNext = pFree->pNext;
            delete pFree;
            isDuplication = 1;
        }
        
        //若重复,则删除第一个重复节点
		if(isDuplication){
			pFree = pCur;			
			pCur = pCur->pNext;			
			pPre->pNext = pCur;
            delete pFree;
			// if(pFree) printf("@");
        }
        //不重复则下移
        else{
            pPre = pPre->pNext;
            pCur = pCur->pNext;
        }
    }
	*pHead = pKid->pNext;
    delete pKid;
}

测试

参见

面22:倒数第K个节点

题面:

给出一个链表,返回倒数第K个节点。

思路:

最直观的思路是遍历到终点,反向遍历K-1次,但是对单链表无可奈何,而且效率不高。

第二种思路可以遍历一次求链表的长度L,第二次遍历L - K + 1个节点。但是需要遍历两次链表。

三种思路更秒,采用双指针,第一个指针先遍历K个节点,随后两个节点一起遍历,直到第一个指针为空,第二个指针就指向了倒数第K个节点。

代码:

ListNode *FindKthToTail(ListNode *pHead, unsigned int K){
    if(pHead == nullptr) return nullptr;
    ListNode *p1 = pHead, *p2 = pHead;
    
    for(int i = 0; i < K; i++){
        if(p1 == nullptr) return nullptr;
        p1 = p1->pNext;
    }
    while(p1!=nullptr){
        p1 = p1->pNext;
        p2 = p2->pNext;
    }
    return p2;
}

这代码写的比剑指offer代码写的优美多了

相关扩展:

相关题目有找出链表的中间节点;判断一个链表是否有环;更难一点判断链表的环的入口节点!

其思路宗旨都是使用两个进度不一样的指针指向不同的节点来解决问题!

面23:链表中的环的入口节点

题面:

给出一个链表,求出其成环的入口节点。

思路:

首先得判断有环,可以使用一个快一慢的两只指针(移动速度分别为2和1)指向链表头。如果链表有环,则快慢指针就一定会相遇。

那么对于有环的链表如何确定其入口节点呢?假设环的中节点有K个,快指针从头先遍历K次之后,快慢指针同时开始遍历,正好两个指针会在入口节点上汇合!

如何确定环中节点呢?这个!可以直接在确定有环后,记录下该节点的位置,再继续遍历直到重新到该节点同时统计经过的节点数量即可。

amazing啊

代码:

ListNode *FindCycleNode(ListNode* pHead){
	if(pHead == nullptr) return nullptr;
    ListNode *pSlow, *pQuick, *pRecord = nullptr ;
    //判断有没有环
    pSlow = pQuick = pHead;
    while(pQuick != nullptr){
	    pQuick = pQuick->pNext;
        if(pQuick) pQuick = pQuick->pNext;
        if(pSlow) pSlow = pSlow->pNext;        
        if(pSlow == pQuick) break;
    }
    if(pQuick == nullptr) return nullptr;
    //确定环内数量
    pRecord = pSlow;
    int numberOfCycle = 0;
    while(pRecord != pSlow){
        numberOfCycle++;
        pSlow = pSlow->pNext;
    }
    //确定环的入口节点
    pSlow = pQuick = pHead;
    for(int i = 0; i < numberOfCycle; i++){
        pQuick = pQuick->pNext;
    }
    while(pSlow != pQuick){
        pQuick = pQuick->pNext;
        pSlow = pSlow->pNext;                
    }
    return pSlow;
}

面24:反转链表

题面:

输入一个链表的头结点,反转该链表并输出反转后的链表的头结点。

思路:

在反转过程中,假设有三个顺序排列的待反转的链表ijk,其中j是待反转的链表。初始化,i为空指针,j为头节点,k为头结点的下一个指针指向的内容(可能为空),并把i的指针指空。在链表反转过程如下:j的指针指向i,然后把ijk分别按次序向后移动。重复执行上述步骤直到j为空。

代码:

ListNode *ReverseList(ListNode *pHead){
    if(pHead == nullptr) return nullptr;
    ListNode *p1 = nullptr, *p2 = pHead, *p3 = pHead->pNext;
    while(p2 != nullptr){
        p2->pNext = p1;
        p1 = p2;
        p2 = p3;
        if(p3) p3 = p3->next;        
    }
    return p2;    
}

面25:合并链表

题面:

将两个链表增序合并成一条链表。

思路:

用两个指针指向两条链表的头结点,用合并数组的思路合并即可。注意一条链表为空后,另一条不为空的链表可以直接连上去。

代码:

ListNode *Merge(ListNode *pHead1, ListNode *pHead2){
    if( pHead1 == nullptr && pHead2 == nullptr){
        return nullptr;
    }else if(pHead1 == nullptr) return pHead2;
    else if(pHead2 == nullpr) return pHead1;
    
    ListNode *p1 = pHead1, *p2 = pHead2, *pHead3 = new ListNode(), *p3 = pHead3;
    
    while(p1 && p2){
        if(p1->value <= p2->value){
            p3->pNext = p1;
            p3 = p1;            
            p1 = p1->pNext;

        }else{
            p3->pNext = p2;
            p3 = p2;
            p2 = p2->pNext;
        }                 
    }
    p3->pNext = nullptr;       
    if(p1){
        p3->pNext = p1;
    }else if(p2){
        p3->pNext = p2;
    }
    ListNode *pFree = pHead3;
    pHead3 = pHead->pNext;
    delete pFree;
	return pHead3;        
}

测试

参见

面35:复杂链表的分解

题面:

给出一个有两个指针的链表数据结构,一个指针1指向下一个节点,另一个指针2可指向任意一个节点,或者为空。将给出的链表复制并返回头结点。

思路:

这题目还是挺不错的!属于比较复杂的题目,而且有思考空间。

将复制的过程分解为两个部分,第一步先不管指针2,复制整个链表;第二步再设置指针2。第一步需要的复杂度为O(N)O(N)。第二步再复制的过程中需要确定复制链表中指针2指向的节点的的位置。

第一种确定位置的思路:就是从原链表遍历寻找原指针指向的节点位置,同样的在复制链表上一起遍历。复杂度为O(N2)O(N2)。

第二种确定位置的思路:直接用hash表记录下原链表中节点和复制链表中对应节点的映射关系。复杂度为O(N)O(N)。是用了空间换时间的思路。

害怕碰撞。

脱离上面的方案的限制,更巧妙的方法来了。链表的顺序遍历远远比随机遍历方便很多,而且指针指向的节点的位置不随链表节点而变化。可以考虑把复制节点直接插入到被复制节点的后面。全部复制完成后,由于原节点的指针2指向的节点的后一个节点就是复制节点的指针2指向的节点,所以可以直接指向。复杂度为O(N)O(N),空间复杂度为O(1)O(1)。

代码:

struct ComplexListNode{
    int value;
    ComplexListNode *pNext;
    ComplexListNode *pSibling;    
}

void CopyNode(ComplexListNode *pHead){
    if(pHead == nullptr) return null;
    ComplexListNode *pNode = pHead;
    while(pNode){
        ComplexListNode *pNew = new ComplexListNode();
        pNew->value = pNode->value;
        pNew->pNext = pNode->pNext;
        pNew->pSibling = nullptr;
        
        pNode->pNext = pNew;
    	pNode = pNew->pNext;
    }    
}

void SetSiblingLink(ComplexListNode * pHead){
    if(pHead == nullptr )return nullptr;
    ComplexListNode *pNode  = pHead;
    while(pNode){
		ComplexListNode *pNext = pNode->pNext;
        pNext->pSibling = pNode->pSibliing->pNext;
        pNode = pNext->pNext;
    }    
}

ComplexListNode *GetComplexList(ComplexListNode *pHead){
    if(pHead == nullptr) return nullptr;
	ComplexListNode *pNode = pHead;
    ComplexListNode *pClonedHead = pNode->pNext;
    ComplexListNode *pClonedNode = pNode->pNext;
    pNode->next = pClonedNode->next;
    pNode = pClneNode->next;
    while(pNode){
        pClonedNode->pNext = pNode->pNext;        
        pNode->pNext = pNode->pNext->pNext;
        pClonedNode = pNode->pNext;
        pNode = pClonedNode->pNext;   
        /*
        //we can write in this way.
        pClonedNode->pNext = pNode->pNext;        
        pClonedNode = pClonedNode->pNext;
		pNode->pNext = pClonedNode->pNext;
        pNode = pNode->pNext;                  
        */
    }
    return pClonedHead;      
}
ComplexListNode *Clone(ComplexListNode* pHead){
    CopyNode(pHead);
    SetSiblingLink(pHead);
    return GetComplexList(pHead);
}

面36:把二叉搜索树转化为双向链表

题面:

如题,要求不创建任何新节点,只能调整树中节点的指向。输出调整后的排序链表。

思路:

可以从递归的角度入手。对于一个节点A,中序遍历到A,则A的左子树已经转化为了链表,连接好AA的左子树的最大节点(前一个指针)的指针则连接完成。

那对于A的右子树的最小节点BA之间的连接,也可以看成B与前一个节点的指针相互链接。那么我们只需要在中序遍历的过程中改变前一个指针的内容即可。

注意一下整棵树的最大的右指针和最小节点的左指针,发现都应该是空,无需额外修改。

对于一个节点A的左右指针,分别指向按顺序排列的旁边两个节点。可以用中序遍历来获取该节点的前一个节点B的指针,并设置好B的右指针和A的左指针。如此就可以在中序遍历的后设置除了最后一个节点的右指针,但是右指针本来就应该是NULL,所以无需修改。

代码:

void AdjustLinkCore(BinaryTreeNode* pRoot, BinaryTreeNode *&preNode, BinaryTreeNode *&pHead){
    if(pRoot == nullptr) return;
  	AdjustLinkCore(pRoot->pLeft, preNode, pHead);

    if(pHead == nullptr) pHead = pRoot;
    pRoot->pLeft = preNode;
    if(preNode) preNode->pRight = pRoot;
    preNode = pRoot;
    
    AdjustLinkCore(pRoot->pRight, preNode, pHead);
}
BinaryTreeNode* AdjustLink(BinaryTreeNode* pRoot){
    BinaryTreeNode *preNode = nullptr;
    BinaryTreeNode *pHead = nullptr;
    AdjustLinkCore(pRoot, preNode, pHead);
    return pHead;
}

面52:两个链表的第一个公共节点

题面:

如题。

思路:

明显地,可以用栈来存储两个链表遍历过程。空间复杂度和时间复杂度都是O(N)O(N)。

换一种想法,能不能直接遍历就使两个链表同时遍历到第一个公共节点。定义两个指针来遍历两条链表。只要让一个指向长链表的节点的指针多走多出的节点,就可以让两个节点同时同序的遍历到公共节点。时间复杂度为O(N+M)O(N+M),空间复杂度O(1)O(1)。

代码:

int GetLenOfList(ListNode *pHead){
    int len = 0;
    ListNode *pNode = pHead;
    while(pNode){
        pNode = pNode->pNext;
        len++;
    }
    return len;
}
ListNode *FindFirstCommonNode(ListNode *pHead1, ListNode *pHead2){
    if(pHead1 == nullptr || pHead2 == nullptr) return nullptr;
    int len1 = GetLenOfList(pHead1);
    int len2 = GetLenOfList(pHead2);
    if(len1 < len2){
        swap(pHead1, pHead2);
        swap(len1, len2);
    }
    int step = len1 - len2;
	ListNode *pNode1 = pHead1;
    ListNode *pNode2 = pHead2;
    while(step){
        pNode1 = pNode->pNext;
        step--;
    }
    while(pNode1 != pNode2){
        pNode1 = pNode1->pNext;
        pNode2 = pNode1->pNext;
    }
    //two pNodes maybe refer to null or the first common node.
    return pNode1;
}

更简单的解法:

双指针遍历两条链表,遍历到结尾则跳到另一条链表上。路径长度的相等一定会有两个指针相遇。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *p1 = headA,  *p2 = headB;
        while(p1 != p2){
            p1 = p1 == nullptr ? headB : p1->next;
            p2 = p2 == nullptr ? headA : p2->next;
        }
        return p1;
    }
};

链表回文判断

234. Palindrome Linked List

O(n)时间,O(1)空间

思路:

朴素的思路:先用快慢指针找到链表中间节点,之后翻转后半部分链表。判断两个链表是否相同。

其中奇数个节点链表需要考虑一下。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode *slow ,*quick;
        slow = quick = head;
        while(quick && quick->next){
            slow = slow->next;
            quick = quick->next->next;
        }
        ListNode *p2 = reverseList(slow), *p1 = head;
        while(p1 && p2){
            if(p1->val != p2->val) return false;
            p1 = p1->next;
            p2 = p2->next;
        }
        return true;
        
    }

    ListNode *reverseList(ListNode* head){
        if(head == nullptr) return head;
        ListNode *per = nullptr, *cur = head, *next = head->next;
        while(cur){
            cur->next = per;
            per = cur;
            cur = next;
            if(next) next = next->next;
        }
        return per;
    }
};

奇偶链表节点分解

非常容易写复杂的题目。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(!(head && head->next)) return head;
        // ListNode *p1 = head, *p2 = new ListNode(), *evenHead = p2, *pre = nullptr;
        // while(p1 && p1->next){
        //     p2->next = p1->next;
        //     p2 = p2->next;
        //     p1->next = p2->next;
        //     pre = p1;
        //     p1 = p2->next;
        // }
        // p2->next = nullptr;    
        // p1 = p1 ? p1 : pre;
        // p1->next = evenHead->next;
        // delete evenHead;
        // return head;
        ListNode *evenHead = head->next, *odd = head, *even = head->next;
        while(even && even->next){
            odd->next = even->next;
            odd = odd->next;
            even->next = odd->next;
            even = even->next;
        }
        odd->next = evenHead;
        return head;
    }
};

删除倒数第N个节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode node, *pre = &node;
        pre->next = head;
        ListNode *quick, *slow;
        quick = slow = pre;
        for(int i = 0; i < n; ++i) quick = quick->next;
        while(quick->next){
            quick = quick->next;
            slow = slow->next;
        }
        ListNode *fordel = slow->next;
        slow->next = fordel->next;
        if(fordel == head){ //删除节点 务必小心:1.删了头结点,需要重置头结点 2.考虑后续节点
            head = fordel->next;
        }
        delete fordel;            
        return head; 

    }
};