Monodyee

这个屌丝很懒，什么也没留下！

热门标签

八大链表OJ笔试题带你手撕单链表_oj 笔试

作者：Monodyee | 2024-05-18 01:08:54

踩

oj 笔试

在这里插入图片描述

八大链表OJ题带你手撕单链表

1. 移除链表元素
- 方法一：（不带哨兵位的）
- 方法二：（带哨兵位的）
2. 反转链表
- 方法一：（三个指针反转方向）
- 方法二：（头插法）
3. 链表的中间节点
4. 链表中倒数第k个结点
5. 合并两个有序链表
6. 链表分割
- 方法一：（带哨兵位的）
- 方法二：（不带哨兵位的）
7. 链表的回文结构
8. 相交链表

1. 移除链表元素

方法一：（不带哨兵位的）

代码：

需要考虑的情况：

正常情况
链表连续几个节点存储的值都是val
链表最开始的节点存储的值是val

图示：

正常情况：（经画图之后，正常情况能够处理链表中连续几个节点存储的值都是val的情况）

头节点存储值为val的情况：

struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode*prev = NULL;
    struct ListNode*cur = head;
    while(cur)
    {
        if(cur->val==val)
        {
            if(prev==NULL)
            {
                struct ListNode* next = cur->next;
                free(cur);
                cur = next;
                head = cur;
            }
            else
            {
                prev->next = cur->next;
                free(cur);
                cur = prev->next;
            }
            
        }
        else
        {
            prev = cur;
            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
22
23
24
25
26
27
28
29
30
31

方法二：（带哨兵位的）

与前面一种方法进行相比，这种方法更为简单，操作起来难度较小并且代码更为简洁，不需要进行区分上面的三种情况。

代码：

struct ListNode* removeElements(struct ListNode* head, int val)//带哨兵位的
{
    struct ListNode*new = malloc(sizeof(struct ListNode));
    new->next = head;
    struct ListNode*prev = new;
    struct ListNode*cur = head;
    while(cur)
    {
        if(cur->val==val)//需要删除的节点
        {
            struct ListNode*next = cur;//next用来存放cur当前的地址，方便后面进行释放
            cur = cur->next;
            prev->next = cur;
            free(next);
        }
        else//不需要删除的节点
        {
            prev = cur;
            cur = cur->next;
        }
    }
    struct ListNode*tmp = new->next;//暂时存储需要返回的地址
    free(new);//把开辟的哨兵位的空间释放掉
    return tmp;
}
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

2. 反转链表

方法一：（三个指针反转方向）

图示：

思路：逐个向后进行遍历，在遍历的同时将next指针的指向变为指向前一个指针，同时返回尾节点（反转后新链表的头节点）

struct ListNode* reverseList(struct ListNode* head)
{
    if(head==NULL)//当链表尾空时，返回的是空链表
    {
        return head;
    }
    else
    {
        struct ListNode*prev = NULL;
        struct ListNode*cur = head;
        struct ListNode*next = head->next;
        while(cur)
        {
            cur->next = prev;
            prev = cur;
            cur = next;
            if(next)
                next = next->next;
        }
        return prev;//返回prev的原因是：当cur为空节点时，cur位于尾节点的下一个，而位于cur的前一个自然就是尾节点，即新的头节点
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

方法二：（头插法）

思路：遍历上面的链表，把节点拿下来头插，但是不创建新的节点。

图示：

注意：此处并没有创建新的节点，其实从本质上来说和上面没有大的区别，只是思想有所差别。

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode*newHead = NULL;
    struct ListNode*cur = head;
    
    while(cur)
    {
        struct ListNode*next = cur->next;
        cur->next = newHead;
        newHead = cur;
        cur = next;
    }
    return newHead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3. 链表的中间节点

思路：

使用两个指针，然后使用两个指针进行遍历，快指针一次跳跃两个节点，慢指针一次跳跃一个节点，当快指针遍历完整个数组的时候，慢指针所处的位置就是中间节点所处的位置。

图示：

代码：

struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode*slow = head;//慢节点
    struct ListNode*fast = head;//快节点
    while(fast&&fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}
1
2
3
4
5
6
7
8
9
10
11

注意：fast和fast->next是不可以进行互换的，因为只有当fast为空的时候就不可能执行到fast->next，所以也就不会出现对空指针进行解引用的情况，一旦互换之后，就可能出现对空指针进行解引用的情况。

4. 链表中倒数第k个结点

思路：其实这个与前面的寻找链表的中间节点相类似，也是使用快慢指针的方法，使快指针先走k个节点，当快指针走到空指针的位置的时候，慢指针所停留的位置就是我们想要找到的节点。

代码：

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
{
    struct ListNode*fast = pListHead;
    struct ListNode*slow = pListHead;
    while(k--)
    {
        if(fast==NULL)
            return NULL;//当k大于链表的长度时返回空指针NULL
        fast = fast->next;
    }
        
    while(fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

注意：

注意下面的两种情况：

当k大于链表的长度的时候
当链表为空链表的时候

上面的这两种情况，都是通过if判断来进行解决的。

5. 合并两个有序链表

思路：

代码：（这是不带哨兵位的）

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    if(list1==NULL)
    {
        return list2;
    }
    if(list2==NULL)
    {
        return list1;
    }
    struct ListNode*tail = NULL;
    struct ListNode*head = tail;
    while(list1&&list2)
    {
        if(list1->val<list2->val)
        {
            if(tail==NULL)
                head = tail = list1;
            else
            {
                tail->next = list1;
                tail = list1;
            }
            list1 = list1->next;
        }
        else
        {
            if(tail==NULL)
                head = tail = list2;
            else
            {
                tail->next = list2;
                tail = list2;
            }
            list2 = list2->next;
        }
    }
    if(list1)
    {
        tail->next = list1;
    }
    if(list2)
    {
        tail->next = list2;
    }
    return 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

（带哨兵位的）

图示：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    struct ListNode*tail = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode*head = tail;
    head->next = NULL;
    while(list1&&list2)
    {
        if(list1->val<list2->val)
        {
            tail->next = list1;
            tail = list1;
            list1 = list1->next;
        }
        else
        {
            tail->next = list2;
            tail = list2;
            list2 = list2->next;
        }
    }
    if(list1)
    {
        tail->next = list1;
    }
    if(list2)
    {
        tail->next = list2;
    }
    return head->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
26
27
28
29
30

6. 链表分割

思路：对原链表进行遍历，然后将小于x的形成一个链表，大于x的形成一个链表，然后将两个链表连接起来就是我们要返回的新链表。

方法一：（带哨兵位的）

图示：

代码：

ListNode* partition(ListNode* pHead, int x) 
{
    struct ListNode* lessTail = (struct ListNode*)malloc(sizeof(ListNode));//作为结尾
    struct ListNode* lessHead = lessTail;//指向新的节点存储元素的值均比x小的链表
    struct ListNode* greaterTail = (struct ListNode*)malloc(sizeof(ListNode));//作为结尾
    struct ListNode* greaterHead = greaterTail;//指向新的节点存储元素的值均比x大或者等于的链表
    struct ListNode* cur = pHead;//用来遍历所给链表的指针
    while (cur)//判断所给链表遍历是否终止
    {
        if (cur->val < x)//连接比x小的链表节点
        {
            lessTail->next = cur;
            lessTail = lessTail->next;
        }
        else//连接大于或者等于x的链表节点
        {
            greaterTail->next = cur;
            greaterTail = greaterTail->next;
        }
        cur = cur->next;
    }
    lessTail->next = greaterHead->next;//连接两个链表形成最后的结果链表
    greaterTail->next = NULL;//将最后一个节点的next置为空
    struct ListNode* list = lessHead->next;//存储返回值，方便free掉开辟的空间
    free(lessHead);
    free(greaterHead);
    return list;
}
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

方法二：（不带哨兵位的）

图示：

1、正常情况：

2、当存储比x小的链表为空时

3、当存储大于x的链表为空时

代码：

ListNode* partition(ListNode* pHead, int x)
{
	struct ListNode* lessHead = NULL;
	struct ListNode* lessTail = NULL;
	struct ListNode* greaterHead = NULL;
	struct ListNode* greaterTail = NULL;
	struct ListNode* cur = pHead;
	while (cur)
	{
		if (cur->val < x)
		{

			if (lessHead == NULL)
			{
				lessTail = cur;
				lessHead = cur;
			}
			else
			{
				lessTail->next = cur;
				lessTail = cur;
			}
		}
		else
		{

			if (greaterHead == NULL)
			{
				greaterTail = cur;
				greaterHead = cur;

			}
			else
			{
				greaterTail->next = cur;
				greaterTail = cur;
			}
		}
		cur = cur->next;
	}
	//应当有三种情况
	//1、存储小于x的链表为空，存储大于x的链表不为空
	//2、存储小于x的链表不为空，存储大于x的链表为空
	//3、存储小于x和存储小于x的链表均不为空
	//后面的两种方法是可以合并的，因为都要进行两个链表的连接，无论存储大于x的链表是否为空，都不影响最后的结果
	if (lessTail == NULL)//判断是否是没有小于x的数据，如果是这种情况，那么就返回存储大于x数据的链表
	{
		return greaterHead;
	}
	
	lessTail->next = greaterHead;//将两个链表进行连接
	if (greaterHead != NULL)
	{
		greaterTail->next = NULL;//将存储大于x的数据的最后一个节点的next置为空指针
	}
	//为什么要进行判定，因为如果直接执行greaterTail->next = NULL属于非法操作，因为当greaterHead等于NULL时，greaterTail也是空指针，执行这行代码就属于对空指针的解引用，属于非法操作
	return lessHead;
}
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

7. 链表的回文结构

思路：(偶数个节点一定不会出现问题，很容易就能想到)

代码：

struct ListNode* middleNode(struct ListNode* head)//求中间节点
{
	struct ListNode* slow = head;//慢节点
	struct ListNode* fast = head;//快节点
	while (fast && fast->next)
	{
		fast = fast->next->next;
		slow = slow->next;
	}
	return slow;
}
struct ListNode* reverseList(struct ListNode* head)//反转链表
{
	if (head == NULL)//当链表尾空时，返回的是空链表
	{
		return head;
	}
	else
	{
		struct ListNode* prev = NULL;
		struct ListNode* cur = head;
		struct ListNode* next = head->next;
		while (cur)
		{
			cur->next = prev;
			prev = cur;
			cur = next;
			if (next)
				next = next->next;
		}
		return prev;
	}
}
bool chkPalindrome(ListNode* head) {
	struct ListNode* mid = middleNode(head);//记录中间节点
	mid = reverseList(mid);//将反转后的新的节点的起始位置赋值给mid
	struct ListNode* cur = head;//用来从头遍历链表
	while (head && mid)
	{
		if (head->val != mid->val)
			return false;
		head = head->next;
		mid = mid->next;
	}
	return true;
}//此处是C++的，true代表1，false代表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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

8. 相交链表

思路：

第一种方法（不推荐）：用listA的每一个节点和listB的每一个节点的地址进行遍历比较，既能判断出是否相交，同时也能找到相交的节点。

第二种方法：先从头找到尾对两个节点同时进行遍历，同时记录两个链表各自的节点数，最后将尾节点进行比较，如果尾节点相同，说明有相交节点，如果不相同，就说明没有相交节点，同时计算出两个链表节点数目的差值，然后使用快慢指针的方法，让较长的链表先走差值步，然后再同时走，两个指针相同的那个点就是我们要求的两个链表相加的点。

图示：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode*tailA = headA;//记录链表A的尾节点
    struct ListNode*tailB = headB;//记录链表B的尾节点
    int lenA = 1;//记录链表A的长度
    int lenB = 1;//记录链表B的长度
    while(tailA->next!=NULL)
    {
        tailA = tailA->next;
        lenA++;
    }
    while(tailB->next!=NULL)
    {
        tailB = tailB->next;
        lenB++;
    }
    
    if(tailA!=tailB)//尾节点不等，所以直接返回NULL
    {
        return NULL;
    }
    //相交，求节点，长的先走差距步，再同时走找交点
    struct ListNode*shortList = headA,*longList = headB;//默认B是较长节点的链表，A是较短的
    if(lenA>lenB)
    {
        longList = headA;
        shortList = headB;
    }
    int gap = abs(lenA - lenB);//gap存储的是节点数的差值

    while(gap--)
    {
        longList = longList->next;//节点数多的先走gap步
    }
    while(longList!=shortList)//两者同时开始进行遍历，在交点处停下
    {
        longList = longList->next;
        shortList = shortList->next;
    }
    return longList;//随便返回一个就行，因为两个都是交点
}
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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/585990