面试题 02.04. 分割链表 - 力扣(LeetCode)
对于该链表OJ,我们两种大的方向:
1.在原链表上修改;2.创建新链表,遍历原链表。
在原链上进行修改:如果该节点的val小于x则继续往后走,如果大于等于x则将该节点尾插到该链表,然后删除该节点,继续遍历;
创建新链表,遍历原链表:对于这种方式也有两种
- 创建一个新链表,遍历原链表,如果节点的val小于x则头插到新链表中,如果大于等于x则尾插到新链表中。
- 创建两个新链表:little和big。遍历原链表,如果节点的val值小于x则尾插到little链表中,如果节点的val值大于等于x则尾插到big链表中,遍历完后,连接这两个新链表即可。
我们今天来实现创建两个新链表的方式来解决问题。
我们在创建链表的时候可以采取带头链表的方式,这样可以避免重复代码的出现。
新链表前的红色圆点就代表着头节点也叫做哨兵位。 我们创建完链表并遍历完之后,就得到了两个大小链表,我们只需要将这两个连接起来就可以了。
我们通过上面代码连接好之后 ,就得到了如图的链表,那么是否可以直接返回little->next?
答案是不行!!! 在该链表中出现了循环结构,程序会陷入死循环。那么怎么解决这个问题呢?
该问题出现的原因是因为big链表的尾节点的next指针指向的不是NULL造成的。我们只需要在连接之前将big链表的尾节点的next指针指向NULL就行了。
下面附上完整代码(注:该代码是leetcode的解题代码,不包括main函数)
typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x)
{
//已知链表为空,直接返回NULL
if(head == NULL)
{
return NULL;
}
//已知链表不为空
//创建两个新链表,为了避免重复代码,可以利用哨兵位
ListNode* little = (ListNode*)malloc(sizeof(ListNode));
ListNode* littletail = little;
ListNode* big = (ListNode*)malloc(sizeof(ListNode));
ListNode* bigtail = big;
//遍历原链表
while(head)
{
if(head->val<x)
{
//小于x,将节点尾插little中
littletail->next = head;
littletail = littletail->next;
}
else
{
//大于等于x,将该节点尾插到big中
bigtail->next = head;
bigtail = bigtail->next;
}
//遍历下一个节点
head = head->next;
}
//退出循环说明已经遍历完了原链表
//修改bigtail指向,否则会陷入死循环
bigtail->next = NULL;
//连接大小链表
//因为这两个链表都是带头链表,所以连接时要指向头结点的下一个节点
littletail->next = big->next;
return little->next;
}
完!