王道数据结构链表习题

发表于2023-07-31|更新于2024-05-05|王道数据结构习题

|字数总计:2.1k|阅读时长:8分钟|阅读量:

链表经典大题

递归删除不带头结点的单链表中所有值为 x 的结点

题目说了是 L 哦。但是我代码写得是 list。偷懒了。

核心思想

板子

核心代码

// 递归删除不带头结点单链表中 x 的值
void Del_x(LinkList & list, int x){
	// 出口
	if(!list) return;
	else if(list -> data == x){
		// 如果当前递归中的结点是应该被删除的结点
		LNode * p = list;
		list = list -> next; // 指向下一个结点
		free(p);
		// 继续寻找
		Del_x(list, x);

		// 下面这三行代码是绝对不能写！！！死循环
		// LNode * p = list -> next;
		// free(list);
		// Del_x(p, x);
	}else{
		// 不是应该被删除的结点
		Del_x(list -> next, x);
	}
}

附赠无头结点的尾插法代码

// 无头结点尾插法建立单链表
void TailInsert(LinkList & list){
	InitList(list);
	
	LNode * r;
	
	int x;
	cin >> x;
	
	while(x != 9999){
		LNode * s = (LNode *)malloc(sizeof(LNode));
		s -> data = x;
		s -> next = NULL;
		// 是第一个结点
		if(!list) list = s;
		else{
			// 平常的尾插
			s -> next = r -> next;
			r -> next = s;
		}
		r = s;
		cin >> x;
	}
}

删除带头结点的单链表中所有值为 x 的结点

核心思想

板子

核心代码

// 删除带头结点单链表中 x 的值
void Del_x(LinkList & list, int x){
	LNode * pre = list, * cur = list -> next;
	
	while(cur){
		// 当前结点是应该被删除的结点
		if(cur -> data == x){
			LNode * q = cur;
			cur = cur -> next;
			pre -> next = cur;
			free(q);
		}else{
			// 当前结点不是应该被删除的结点
			pre = cur;
			cur = cur -> next;
		}
	}
}

从尾到头反向输出带头结点单链表中每个结点的值

核心思想

利用栈的思想

核心代码

// 反向输出链表中每个结点的值
// 0.在 main 函数中，调用要注意！
// 1.Reverse_Print（list -> next); 带头结点
// 2.Reverse_Print（list); 不带头结点
void Reverse_Print(LinkList list){
	// 出口
	if(!list) return;
	
	// 入栈
	Reverse_Print(list -> next);
	
	// 出栈
	cout << list -> data << " ";	
}

删除带头结点单链表中的唯一最小值

核心思想

利用 min_pre、cur 两个指针
利用线性表寻找最小值算法思想
min_pre用来更新保存，目前已知最小值结点的前一个结点

核心代码

// 删除单链表中唯一最小值结点
bool Del_Min(LinkList & list){
	// 如果是空表或只有头节点
	if(!list || !list -> next) return false;
	// 经典前后指针
	LNode * pre = list, * cur = list -> next;
    // 保存最小值结点的前一个结点
	LNode * min_pre = list;
	
	// 假设最小值是第一个节点
	LNode * t = cur;
	// 打擂台
	while(cur){
		// 如果发现比最小值还要小的
         // 打赢了，新的当 t
		if(cur -> data < t -> data){
			t = cur;
             // pre 作为 新的min_pre
			min_pre = pre;
		}
		// 俩指针后移
		pre = cur;
		cur = cur -> next;
	}

	// 删除擂主
	min_pre -> next = t -> next;
	free(t);
	
	return true;
}

带头结点的单链表逆置

核心思想

准备pre、cur、r 3个指针，cur指向pre。

核心代码

// 单链表就地逆置
bool Reverse_LinkList(LinkList & list){
	// 空表或者只有头结点或者只有一个元素
	if(!list || !list -> next || !list -> next -> next) return false;
	
	LNode * pre = list , * cur = list -> next;
	LNode * r = cur -> next;
	// NULL <- cur <- r
	cur -> next = NULL;
	
	while(r){
		pre = cur;
		cur = r;
		r = r -> next;
		cur -> next = pre;
	}
	
	// cur才是真正的主元素，r只是拿来判断的边界条件
	list -> next = cur;
	
	return true;
}

单链表的插入排序

核心思想

核心代码

两个单链表的公共结点

核心思想

假设有两个单链表A和B。

单链表A长度为：a

单链表B长度为：b

无非两种情况：相交和不相交

可以利用a + c + b ＝ b + c + a。求出交点。

这是不相交的情况。

a + b ＝ b + a。

相遇为NULL，返回NULL。

公式恒成立。

核心代码

LNode * findFirstCommonNode(LinkList headA, LinkList headB) {
    LNode * p = headA , * q = headB;
    
    while(p != q){
        p = p ? p -> next : headB;
        q = q ? q -> next : headA;
    }

    return p;
}

将原单链表A分裂为：`奇A表`和`偶B表`

核心思想

奇偶序号计数i。
ra和rb尾指针。
将A的next先置空，后面会通过ra来增加结点。
根据i的奇偶，在ra或者rb后面增加结点p，再更新ra或rb。
ra和rb的next需要置空。

核心代码

// 将原单链表A分裂为：`奇A表`和`偶B表`
LinkList Re_Create(LinkList & A){
	// 准备B表
	LinkList B = (LNode *)malloc(sizeof(LNode));
	B -> next = NULL;
	
	// 准备工作
	LNode * ra = A , * rb = B; // A 和 B 的尾指针
	LNode * p = A -> next; // 遍历准备工作
	
	// A 表断开
	A -> next = NULL;
	
	// 奇偶序列计数
	int i = 0;
	while(p){
		i++;
		// 奇
		if(i % 2){
			ra -> next = p;
			ra = p;
		}else{
			// 偶
			rb -> next = p;
			rb = p;
		}
		p = p -> next;
	}
	// 尾指针置空
	ra -> next = NULL;
	rb -> next = NULL;
	
	return B;
}

递增有序的单链表，去除相同的元素

核心思想

核心代码

带头结点的循环双链表是否对称

核心思想

设置两个指针p和q。往两个不同的方向走
结点数是奇数和偶数，是难点。2n + 1和2n。

核心代码

bool Symmetry(DLinkList list){
    DNode * p = list -> next , * q = list -> prior;
    // 第二个条件容易写成 p -> next != q;
    while(p != q && q -> next != p){
        if(p -> data == q -> data){
            p = p -> next;
            q = q -> prior;
        }else return false;
    }
    return true;
}

单链表判断是否有环

核心思想

慢指针一步一步走，快指针两步两步走
无环：快指针必定会先到达终点（NULL）
有环：俩指针会相遇，相遇之后，让慢指针回到起点，再让快慢指针同步速度，一步一步走
当再次相遇的时候，那个点就是环的入口

核心代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        ListNode * slow = head , * fast = head;

        while(fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
            // 有环，相遇了
            if(slow == fast) break;
        }
        // 如果fast是空，那么代表无环，否则代表有环，并且slow == fast成立
        // 而且，如果while循环条件一开始就没满足，那么代表head是空节点亦或者长度为1
        if(!fast || !fast->next) return NULL;
        // slow == fast ， 有环
        // 让slow回去，fast和slow以同样的速度走，再次相遇就是环的入口结点
        slow = head;
        while(slow != fast){
            slow = slow -> next;
            fast = fast -> next;
        }
        // 再次相遇了
        return slow;
    }
};

作者：麦高芬
链接：https://www.acwing.com/solution/content/153752/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

单链表倒数第 k 个值

核心思想

两个指针p和q
先让它们两个相距k
当q遍历完的时候，p就是倒数第k个节点

核心代码

int Search_K(LinkList list, int k){
	// 计数
	int count = 0;
	
	LNode * p = list -> next, * q = list -> next;
	
	while(q){
		// 先让q走 k 步
		if(count < k){
			count++;
			q = q -> next;
		}else{
			p = p -> next;
			q = q -> next;
		}
	}
	
	// 查找失败
	if(count < k) return 0;
	else cout << p -> data << endl;
	
	return 1;
}

重排链表

核心思想

先遍历一遍链表，获取链表的长度。
根据获取到的链表长度，获取链表中间的结点。(向上取整)
反转后半段链表。
合并前半段链表和反转后的后半段链表。

核心代码

void rearrangedList(ListNode* head) {
        if(!head->next) return;
        // 获取链表的长度
        int len = 0;
        for(auto p = head ; p ; p = p -> next) len++;
    
        // 链表中间的结点
        int left = (len + 1) >> 1;
        auto a = head;
        for(int i = 0 ; i < left - 1 ; i++) a = a -> next;
    	// 反转后半段链表，b在前，c在后  
        auto b = a -> next , c = b -> next;
    	// a->next 是为了从中间将链表截断；b->next 是因为此时的 b 是反转后链表的结尾元素
        a -> next = b -> next = NULL;
        
        while(c){
            auto p = c -> next;
            c -> next = b;
            b = c; c = p;
        }
    
        // 合并链表，注意此时 b 指向反转链表头部
        auto p = head;
        auto q = b;
        // o -> o -> o -> NULL (p)
        // o -> o -> o -> NULL (q)
        while(q){
            auto o = q -> next;
            q -> next = p -> next;
            p -> next = q;
            p = q -> next;
            q = o;
        }
    }

文章作者: Phbeats

文章链接: https://blog.phbeats.cn/posts/78005f2f1e1c/

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Phbeats-Blog！

王道数据结构习题

相关推荐

王道数据结构顺序表习题

评论