• 数据结构——常见链表算法题

    数据结构——常见链表算法题（C++运行）

    本文介绍常见的有关链表的算法题，值得一提的是，该代码无需在力扣上，可在本地运行成功。
    题目八道：
    1.反转链表
    2.移除链表中的重复节点
    3.查找链表中的中间节点
    4.找到链表中的倒数第k个节点
    5.合并两个升序链表，并同样按照升序排列
    6.判断是否为环形链表
    7.查找两链表的交点，相交链表
    8.判断是否为回文链表（空链表和单节点链表也算）

    创建链表类和方法类以及打印链表方法

    #include 
using namespace std;

//定义链表结构
class ListNode{
public:
    int val;
    ListNode* next;
    //结构体构造函数
    ListNode(int x);
    ListNode* listNode_create();

//默认访问权限为private   
};

ListNode::ListNode(int x=0):val(x),next(NULL)
{
}//列表初始化用法

ListNode* ListNode::listNode_create(){
    cout<<"请输入链表长度:";
    int num =0;
    cin>>num;
    int listValue=0;
    ListNode * head ;
    ListNode * tempNode;
    ListNode * node = head;
    head = NULL;
    tempNode = NULL;

    for (int i =0;i<num;i++){
        if(head == NULL){
            head = this;
            node = head;
        }else{
            node = new ListNode;
            cout<<"输入链表节点的值node->val:";
            cin>>node->val;
            tempNode->next = node;
        }
        tempNode = node;
        tempNode->next = NULL;    
    }
    cout<<"链表完成创建"<<endl;
    return head;
} 

class Solution{
    public:
        Solution();
        ListNode* reverseNode(ListNode* head);//反转链表
        ListNode* removeSameNode(ListNode* head);//移除重复链表
        ListNode* findLastKnode(ListNode* head,int k);//找出倒数第K个链表节点
        ListNode* midNode(ListNode* head);//找出链表中间节点,注意偶数时返回第一个节点和第二个节点的循环结束区别
        ListNode* mergeListNode(ListNode* list1,ListNode* list2);//两个升序链表合并成一个升序链表
        ListNode* circleListNode(ListNode* head);//找出环形列表的节点
        ListNode* findcrossingListNode1(ListNode* list1,ListNode* list2);//查找相交节点,方法一
        ListNode* findcrossingListNode2(ListNode* list1,ListNode* list2);//查找相交节点,方法二
        bool findPalindrome(ListNode* head);//判断是否为回文列表
};

Solution::Solution(){}

//打印链表
void printList(ListNode* head){
    cout<<"链表:head";
    ListNode* temp = head;
    while(temp != NULL){
        cout<<"<<"<<temp->val;
        temp = temp->next;
    }
}

//打印链表,k最大打印个数
void printList(ListNode* head,int k){
    cout<<"链表：head";
    ListNode* temp = head;
    while(temp != NULL && k>0){
        cout<<"<<"<<temp->val;
        temp = temp->next;
        k--;

    }

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85

    1.反转链表

    思路：定义三个链表:former:存储完成反转的前一个链表，mid:正在处理的节点，latter:下一个待处理的节点。

    方法：

    ListNode* Solution::reverseNode(ListNode* head){
    if(head==NULL || head->next == NULL){
        return head;
    }

    ListNode* former = NULL;//保存前一个链表节点
    ListNode* mid = head;//正在处理的中间节点
    ListNode* latter = NULL;//保存下一个需要处理的节点
    while(mid != NULL){
        latter = mid->next;//保存下一个节点地址
        mid->next = former;//反转当前节点，next指向上一个链表节点
        former = mid;//former储存节点
        mid = latter;//处理下一个节点
    }
    return former;//返回节点
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    main函数：

    int main(){
    
    ListNode* head = new ListNode(1);
    ListNode* node2 = new ListNode(1);
    ListNode* node3 = new ListNode(5);
    ListNode* node4 = new ListNode(3);
    ListNode* node5 = new ListNode(1);
    ListNode* node6 = new ListNode(1);
   
    head->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;
    node5->next = node6;
	
    Solution* s = new Solution();
    //反转链表
    cout<<"原链表:";
    printList(head);
    cout<<endl<<"反转后列表:";
    head = s->reverseNode(head);
    printList(head);
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    在这里插入图片描述

    2.移除链表中的重复节点

    使用数组，第一次出现的对应数组值置，随后再遇到数组值为1的节点将其移除。“空间换时间”

    方法：

    ListNode* Solution::removeSameNode(ListNode* head){
    if(head == NULL||head->next == NULL){
        return head;
    }
    ListNode* cur = head;//正在识别的listnode
    ListNode* pre = head;//已经处理好的listNode
    int numIndex[10001] = {0};
    //numIndex[pre->val] = 1;
    while(cur != NULL){
        if(numIndex[cur->val] == 0){
            numIndex[cur->val] = 1;
            pre = cur;
            cur = cur->next;
            
        }else{
            pre->next = cur->next;
            cur = cur->next;
        }
    }
    return head; 
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    main函数：

    int main(){
    ListNode* head = new ListNode(1);
    ListNode* node2 = new ListNode(1);
    ListNode* node3 = new ListNode(5);
    ListNode* node4 = new ListNode(3);
    ListNode* node5 = new ListNode(1);
    ListNode* node6 = new ListNode(1);
  
    head->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;
    node5->next = node6;
    Solution* s = new Solution();
    cout<<"原链表:";
    printList(head);
    cout<<endl<<"移除重复节点后:";
    s->removeSameNode(head);
    printList(head);
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    在这里插入图片描述

    3.查找链表中的中间节点

    快慢指针，快指针走两步，慢指针走一步，最终快指针结束循环，慢指针到达中点。
    注意：此处规定：为偶数，返回第二个节点，则判断条件为fast !=NULL && fast->next !=NULL;
    若想要返回第一个节点则:fast->next != NULL && fast->next->next != NULL.

    方法：

    //找出链表中间节点,注意偶数时返回第一个节点和第二个节点的循环结束区别
//返回第二个节点:while(fast != NULL && fast->next !=NULL)
//返回第一个节点:while(fast->next != NULL && fast->next->next !=NULL)
ListNode* Solution::midNode(ListNode* head){
    ListNode* slow = head;
    ListNode* fast = head;
    if(head == NULL && head->next == NULL){
        return head;
    }
    while(fast != NULL && fast->next !=NULL){
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    main函数：

    int main(){
    
    ListNode* head = new ListNode(1);
    ListNode* node2 = new ListNode(1);
    ListNode* node3 = new ListNode(5);
    ListNode* node4 = new ListNode(3);
    ListNode* node5 = new ListNode(1);
    ListNode* node6 = new ListNode(1);
   
    head->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;
    node5->next = node6;
   
    Solution* s = new Solution();
    cout<<"原链表:";
    printList(head);

	cout<<endl<<"返回链表的中间节点:";
    ListNode* mid = s->midNode(head);
    printList(mid);
	return 0;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    在这里插入图片描述

    4.找到链表中的倒数第k个节点

    双指针，一个指针比另一个指针快走k个节点，速度相同，最终快走的节点到头后，另一个指针所在节点为倒数第k个节点。

    方法：

    ListNode* Solution::findLastKnode(ListNode* head,int k){//快慢指针
    ListNode* slow = head;
    ListNode* fast = head;
    int i =0;
    for(i=0;i<k;i++){
        fast=fast->next;
    }

    while(fast!=NULL){
        fast=fast->next;
        slow=slow->next;
    }
    return slow;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    main函数：

    int main(){
    
    ListNode* head = new ListNode(1);
    ListNode* node2 = new ListNode(1);
    ListNode* node3 = new ListNode(5);
    ListNode* node4 = new ListNode(3);
    ListNode* node5 = new ListNode(1);
    ListNode* node6 = new ListNode(1);
    
    
    head->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;
    node5->next = node6;
    //node6->next = node3;

    Solution* s = new Solution();
    cout<<"原链表:";
    printList(head);
    cout<<endl<<"返回倒数第k个链表节点:";
    ListNode* temp = s->findLastKnode(head,3);
    printList(temp);
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    在这里插入图片描述

    5.合并两个升序链表，并同样按照升序排列

    重新定义一个链表，两个链表依次比较，较小值拼接到新建链表上，若有一链表全部拼接完，直接将另一个链表（已升序排列）的剩余依次拼接到新建链表上。

    方法：

    ListNode* Solution::mergeListNode(ListNode* list1,ListNode* list2){
    if(list1 == NULL){
        return list2;
    }
    if(list2 == NULL){
        return list1;
    }
    ListNode* head = new ListNode();
    ListNode* cur = head;
    while(list1 != NULL && list2 != NULL){
        if(list1->val < list2->val){
            cur->next = list1;
            list1=list1->next;
        }else{
            cur->next = list2;
            list2=list2->next;
        }
        cur = cur->next;
    }
    if(list1 ==NULL){
        cur->next = list2;
    }else{
        cur->next = list1;
    }
    return head->next;//返回head的后一个链表节点
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    main函数：

    int main(){ 
    ListNode* head = new ListNode(1);
    ListNode* node2 = new ListNode(2);
    ListNode* node3 = new ListNode(3);
    ListNode* node4 = new ListNode(4);
    ListNode* node5 = new ListNode(5);
    ListNode* node6 = new ListNode(6); 
    head->next = node2;
    node2->next = node3;
    node3->next = node4;            
    Solution* s = new Solution();
    ListNode* head2 = new ListNode(0);
    head2->next = node5;
    node5->next = node6;
    
    cout<<"原链表list1:";
    printList(head);
    cout<<"原链表list2:";
    printList(head2);

	cout<<endl<<"返回合并后的链表:";
    ListNode* mergeNode = s->mergeListNode(head,head2);
    printList(mergeNode);
	return 0；
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    6.判断是否为环形链表

    在这里插入图片描述
    快慢指针思路

    方法：

    //找出环形链表的节点,快慢指针，有环则返回环节点，无环则返回NULL
ListNode* Solution::circleListNode(ListNode* head){
    ListNode* fast = head;
    ListNode* slow = head;
    while(fast !=NULL && fast->next != NULL){
        fast=fast->next->next;
        slow=slow->next;
        if(slow == fast){
            fast = head;
            while(fast != slow){
                fast = fast->next;
                slow = slow->next;
            }
            return slow;
        }
    }
    return NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    main函数：

    int main(){
    
    ListNode* head = new ListNode(1);
    ListNode* node2 = new ListNode(2);
    ListNode* node3 = new ListNode(3);
    ListNode* node4 = new ListNode(4);
    ListNode* node5 = new ListNode(5);
    ListNode* node6 = new ListNode(6);
   
    head->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;
    node5->next = node6;
    node6->next = node3;
	Solution* s = new Solution();
    cout<<"原链表list1:";
    printList(head,10);
	cout<<endl<<"返回环形后的链表:";
    ListNode* circlehead = s->circleListNode(head);
    printList(circlehead,10);
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    7.查找两链表的交点，相交链表

    //查找相交节点,方法一，a+c+b=d+c+b;最后相较于交点
 ListNode* Solution::findcrossingListNode1(ListNode* list1,ListNode* list2){
    ListNode* p=list1;
    ListNode* q=list2;
    while(p !=q){
        if(p==NULL){
            p = list2;
        }else{
            p = p->next;
        }
        if(q == NULL){
            q = list1;
        }else{
            q = q->next;
        }
    }
    return q;
}

//查找相交节点，方法二，迭代法
ListNode* Solution::findcrossingListNode2(ListNode* list1,ListNode* list2){
    ListNode* p=list1;
    ListNode* q=list2;
    while(p !=NULL){
        q=list2;
        while(q !=NULL){
            if(p == q){
                return p;
            }
            q=q->next;
        }
        p = p->next;
    }
    return p;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35

    main函数：

    int main(){
    ListNode* head = new ListNode(1);
    ListNode* node2 = new ListNode(2);
    ListNode* node3 = new ListNode(3);
    ListNode* node4 = new ListNode(4);
    ListNode* node5 = new ListNode(5);
    ListNode* node6 = new ListNode(6);
    
    head->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;
    node5->next = node6;
    Solution* s = new Solution();
    ListNode* head2 = new ListNode(0);
    head2->next = node3;
    cout<<"原链表list1:";
    printList(head);
    cout<<"原链表list2:";
    printList(head2);

	cout<<endl<<"返回交点节点:";
    ListNode* crossingNode = s->findcrossingListNode1(head,head2);//方法一
    //ListNode* crossingNode = s->findcrossingListNode2(head,head2);//方法二
    printList(crossingNode);
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    在这里插入图片描述

    8.判断是否为回文链表（空链表和单节点链表也算）

    提取中间节点，反转链表，再比较是否相等

    //判断是否为回文列表：先取中间节点（如为偶数取第二个），然后链表反转，最后判断前面链表是否与后面链表相同
bool Solution::findPalindrome(ListNode* head){
    ListNode* list1 = head;
    ListNode* list2 = head;
    //if判断语句可有可无，不影响结果输出
    if(head==NULL || head->next == NULL){
        return true;
    }
    
    //去链表中间节点
    while(list1 != NULL && list1->next != NULL){
        list1 = list1->next->next;
        list2 = list2->next;
    }

    //反转链表
    ListNode* former = NULL;
    ListNode* mid = list2;
    ListNode* latter = NULL;

    while(mid !=NULL){
        latter = mid->next;
        mid->next = former;
        former = mid;
        mid = latter;
    }

    list1 = head;

    while((former !=NULL) &&(list1 !=NULL)){
        if(former->val != list1->val){
            return false;
        }
        former = former->next;
        list1 = list1->next;
    }
    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38

    main函数：

    int main(){
    ListNode* head = new ListNode(1);
    ListNode* node2 = new ListNode(2);
    ListNode* node3 = new ListNode(3);
    ListNode* node4 = new ListNode(3);
    ListNode* node5 = new ListNode(2);
    ListNode* node6 = new ListNode(1);
    head->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;
    node5->next = node6;
	Solution* s = new Solution();
    cout<<"原链表:";
    printList(head);
    //判断是否为回文链表
    bool palindromeFlag = s-> findPalindrome(head);//空链表和只有一个节点的链表也为回文链表
    if(palindromeFlag == true){
        cout<<"该链表为回文链表";
    }else{
        cout<<"该链表不为回文链表";
    } 
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    在这里插入图片描述

  • 相关阅读:
    常量指针和指针常量
    wxFormBuilder + Python 工具开发第三章-日记本工具树节点增、改、删功能
    frp配置http服务使用子域名不通不生效的问题记录
    vue-element-admin 常用工具、命令、安装及报错处理方法、注意事项等
    分享一个springboot+uniapp基于微信小程序的校医务室健康服务系统源码 lw 调试
    解决nginx代理后，前端拿不到后端自定义的header
    python+selenium模拟键盘使用ESC退出某个页面中的小页面
    什么是重绘和回流（重排）？什么情况下会用到？如何减少
    pytorch单机多卡及常见问题
    【前端设计模式】之状态模式
  • 原文地址：https://blog.csdn.net/secretboys/article/details/126390739