数据结构--单链表OJ题

2024-05-02 16:27
32人已看

例1：反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

解：这道题有递归和迭代两种反转链表的方式。

如果是迭代的话，我们需要使用的是三指针法。首先保证链表不为空，然后创建三个指针(n1、n2、n3)，开始时将n1赋值为NULL，n2赋值为head，n3赋值为head->next。随后进行链表遍历，先让n2->next = n1，然后n1 = n2、n2=n3、当n3！= NULL时，n3也向后移动一个节点，即n3 = n3->next。在循环结束后，n1就是我们新的头结点。

struct ListNode* reverseList(struct ListNode* head) 
{
    if(head == NULL)
    {
        return head;
    }
   else
   {
     //三指针法
    struct ListNode*n1;
    struct ListNode*n2;
    struct ListNode*n3;
    n1 = NULL;
    n2 = head;
    n3 = head->next;
    //
    while(n2)//n2 = NILL时退出循环
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n2)
        {
        n3 = n2->next;
        }
    }
    return n1;//返回新的头节点
   }
}

如果是递归法的话，我们首先要判断链表的头结点和其下一个节点是否为空，如果为空就不需要反转，直接返回头指针；如果不为空，我们就再次调用本函数，但是参数变成了head->next。随后我们将当前节点的下一个节点的指针指向当前节点，然后将当前节点的指针置为空指针。代码如下：

// 递归反转链表函数
struct ListNode* reverseList(struct ListNode* head) 
{
    if (head == NULL || head->next == NULL) 
    {
        return head;
    }

    // 递归调用反转链表的函数
    struct ListNode* new_head = reverseList(head->next);

    // 将当前节点的下一个节点的指针指向当前节点，然后将当前节点的指针指向空
    head->next->next = head;
    head->next = NULL;

    return new_head;
}

例2：移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

提示：

列表中的节点数目在范围 [0, 10^4] 内
1 <= Node.val <= 50
0 <= val <= 50

解：这道题你可以选择删除链表中的元素，但我个人认为创建新链表是更简单的方法。

首先我们创建好新的头指针(newhead)和尾指针(newtail)并赋值为NULL，考虑原链表是否为空是必不可少的一步，然后我们就要开始尾插节点了。我们创建一个pcur的临时变量来代替头指针进行遍历链表的操作。当pcur->val不等于val时，我们就尾插代码，这里尾插代码分为空链表的尾插，和非空链表的尾插，空链表的尾插就是newhead=NULL时，我们将newhead和newtail都赋值为第一个不为val的节点，成为非空链表之后，我们就进行简单的尾插就可以了。在循环结束后我们要记得把newtail->next置为空。代码如下：

struct ListNode* removeElements(struct ListNode* head, int val) 
{
    struct ListNode* newhead = NULL;
    struct ListNode* newtail = NULL;
    //空链表
    if(head == NULL)
    {
        return NULL;
    }
    //非空链表
    struct ListNode* pcur = head;
    while(pcur)
    {
        if(pcur->val != val)
        {
            if(newhead == NULL)
            {
                newhead = newtail = pcur;
            }
            else
            {
                newtail->next = pcur;
                newtail = newtail->next;
            }
        }
        pcur = pcur->next;
    }
    if(newtail)
        newtail->next = NULL; 

    return newhead;
}

例3：链表的中间节点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

提示：

链表的结点数范围是 [1, 100]
1 <= Node.val <= 100

解：

这道题我推荐使用快慢指针来做，快和慢只是形容词。我们创建两个指针（slow和fast），将两个指针都赋值为头指针head，然后进行循环，slow一次前进一个节点，fast一次前进两个节点，当fast或者fast->next为空指针时，循环结束，而slow指向的节点就是中间节点。

代码演示：

struct ListNode* middleNode(struct ListNode* head) 
{
    //快慢指针
    struct ListNode* slow,*fast;
    slow = head,fast = head;

    //慢指针走一步，快指针走两步，fast到头就停止循环
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;

}

例4：环形链表的约瑟夫问题

编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。下一个人继续从 1 开始报数。n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？

数据范围： 1≤𝑛,𝑚≤100001≤n,m≤10000

进阶：空间复杂度 𝑂(1)，时间复杂度 𝑂(𝑛)

解：

约瑟夫的环形链表问题非常经典，我们用图来讲解。假设环中有五个节点，我们在申请节点时将它们一次按序号连起来即可。

但这样还不够，因为我们需要的是成环的链表，所以我们还需要把首尾节点也连接起来。

接下来就是点名环节，因为我们需要把1号作为第一名，所以我们选择返回为节点，而不是头结点，为此我们创建了prev、pcur两个节点，prev指向尾节点，pcur->指向prev->next 也就是头结点。然后我们继续执行后续操作：

假设m为2，当pcur指到2时我们需要释放名次为2的节点，但在释放之前，我们要将这个节点的前一个节点和后一个节点相连，这也是prev存在的意义。（prev->next = pcur->next）

删掉点之后，我们将pcur赋值为它的下一个节点，并标记为名次1，继续循环。当环中只剩下一个节点是时，我们就退出循环，并返回该节点的值。代码如下：

typedef struct ListNode ListNode;
 //申请节点
ListNode* BuyNode(int i)
{
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	if (node == NULL)
	{
		perror("BuyNode:malloc");
		exit(1);
	}
	else
	{
		node->val = i;
		node->next = NULL;
	}
	return node;
}



//创建环形链表
ListNode* CircleList(int n)
{
	ListNode* newnode = BuyNode(1);
	ListNode* phead = newnode;
	ListNode* ptail = phead;
	for (int i = 2; i <= n; i++)
	{
		ptail->next = BuyNode(i);
		ptail = ptail->next;
	}
	//链接首尾节点成环
	ptail->next = phead;
	//返回尾节点
	return ptail;
}

int ysf(int n, int m)
{
	//创建环形链表
	ListNode* prev = CircleList(n);
	ListNode* pcur = prev->next;
	int count = 1;
	while (pcur->next != pcur)
	{
		if (count == m)
		{
			prev->next = pcur->next;
			free(pcur);
			pcur = prev->next;
			count = 1;
		}
		else
		{
			prev = pcur;
			pcur = prev->next;
			count++;
		}
	}
	int del = pcur->val;
	free(pcur);
	pcur = NULL;
	return del;
}

例5：合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

解：

这道题的解法和顺序表的合并大同小异。我们首先要判断有无空链表，有的话，直接返回另一个链表，没有继续向下执行，我们分别为两个链表的头结点创建一个临时指针变量代替头结点去遍历链表，然后申请一个新的头结点和尾节点，通过对两个链表的值的对比选出较小的节点进行尾插，当有一个链表遍历结束时，我们直接把另一个链表的剩余节点尾插到新链表后面。因为头结点只起到了站岗的作用，所以在返回新的节点之前，我们要释放头结点。这样我们就讲完了代码的思路，代码如下：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{
    if(list1 == NULL)
    {
        return list2;
    }
    if(list2 == NULL)
    {
        return list1;
    }
    struct ListNode* l1 = list1;
    struct ListNode* l2 = list2;

    struct ListNode*newhead,*newtail;
    newhead = newtail = (struct ListNode*)malloc(sizeof(struct ListNode));

    while(l1 && l2)
    {
        if(l1->val < l2->val)
        {
            //把l1拿下来
            newtail->next = l1;
            newtail = newtail->next;
            l1 = l1->next;
        }else{
            //把l2拿下来
            newtail->next = l2;
            newtail = newtail->next;
            l2 = l2->next;
        }
    }
    if(l1)
    {
        newtail->next = l1;
    }
    if(l2)
    {
        newtail->next = l2;
    }
    //动态申请的空间手动释放
    struct ListNode* ret = newhead->next;
    free(newhead);
    newhead = NULL;
    
    return ret;
}