C++学习笔记——链表基础算法

链表

链表的基本单元为一个结构体，其中包含一个值和指向下一个链表的指针，在增减插入成员方面具有较高的效率。

删除链表中的给定节点

当链表头节点给定的时候，可以通过遍历寻找。也可以不依赖链表头节点，直接对给定节点本身操作，删除该节点。

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
    
};
//删除链表中的节点
//给定一个链表和给定一个节点，将给定节点从链表中取出，保持前后顺序不变
void deleteNode(ListNode* node) {
    node->val = node->next->val;//将后一个节点的信息复制到当前节点
    node->next = node->next->next;//当前节点指向次次节点，以丢掉重复节点
}
1
2
3
4
5
6
7
8
9
10
11
12

删除倒数第几个节点

//删除链表的倒数第N个节点
ListNode* removeNthFromEnd(ListNode* head, int n) {
    //首先确定节点位置
    ListNode* dummy = new ListNode(0, head);//创建哑指针指向head，排除head的特殊性
    ListNode* tem_node = head;
    ListNode* rem_node = dummy;

    for (int i = 0; i < n; i++)//判断是否是指定位置
    {
        tem_node = tem_node->next;
    }
    while (tem_node != nullptr)
    {
                rem_node = rem_node->next;
                tem_node = tem_node->next;
    }
        rem_node->next = rem_node->next->next;
        
        return dummy->next;
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

反转链表

反转链表的方法比较多，可以利用栈等数据结构，实现链表的反转。也可以通过辅助链，即双链实现。既可以通过迭代，也可以通过递归实现。以双链法为例

ListNode* reverseList(ListNode* head) {
    ListNode* ans = nullptr;
    ListNode* tem = head;
    while (head)
    {
        tem = head->next;
        head->next = ans;
        ans = head;
        head = tem;

    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

其思想就是不断的将当前节点指向后一节点的链接取消，改为指向前一节点。

合并两个有序链表

//合并两个有序链表
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode* l1 = list1;
    ListNode* l2 = list2;
    ListNode* preHead = new ListNode(-1);

    ListNode* prev = preHead;
    while (l1 != nullptr && l2 != nullptr) {
        if (l1->val < l2->val) {
            prev->next = l1;
            l1 = l1->next;
        }
        else {
            prev->next = l2;
            l2 = l2->next;
        }
        prev = prev->next;
    }

    // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
    prev->next = l1 == nullptr ? l2 : l1;

    return preHead->next;
}

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