您现在的位置是:首页 >学无止境 >LeetCode 牛客单链表OJ题目思路分享网站首页学无止境
LeetCode 牛客单链表OJ题目思路分享
反转链表
链接: link
题目描述:
题目思路:
方法1:改变链表链接的方向
方法1思路:
这力我们需要三个指针n1 n2 n3方便我们进行迭代
初始化n1指向NULL,n2指向第一个节点,n3指向第2个节点,下面是n1 n2 n3 3个指针移动的过程。
1、改变第一个指针n1的指向,链表反转后,第一个节点的指针域指向的是NULL,就上图来看,也就是n2->next=n1;
2、改变指向后,我们接下来的操作就是移动3个指针继续进行链接变向的操作。下面是如何变动三个指针的过程:
将n2的值赋给n1,n3的值赋给n2,n3再向下走一步。
3、下面进行的步骤就是反转链接方向:n2->next = n1。
上述过程就是我们反转的最核心步骤,下面是本题循环终止条件和Bug点:
这里我们要注意,本题要清楚的是,当n1指向最后一个节点的时候,循环就终止了,但是这个点并不是我们所需要的循环的终止条件,循环终止条件是n2为空指针。
本题大致雏形就出来了,但是我们实际进行运行的时候,还会出现空指针的问题,问题的来源就在于n3。
当n2不为空指针,并且n2此时已经指向最后一个节点时,n3已经为空指针,当n2为空指针的时候,n3也要向下走,这就造成了空指针的问题,所以我们要进行处理的是n3,n3不为空指针的时候,n3才可以继续向下走。
最后状态如下图所示:最后我们只需要返回n1就可以了
代码实现:
struct ListNode* reverseList(struct ListNode* head)
{
if(head==NULL)
{
return NULL;
}
struct ListNode* n1 = NULL;
struct ListNode* n2 = head;
struct ListNode* n3 = head->next;
while(n2)
{
//改变链表指向
n2->next = n1;
//迭代
n1 = n2;
n2 =n3;
if(n3)//如果n3不为空,则n3向下走
{
n3 = n3->next;
}
}
return n1;
}
方法2:依次取节点进行头插
方法2思路:
定义如上图3个指针变量,cur指向当前节点,next指向当前节点的下一个节点,rhead是链表反转之后新的头。
初始化rhead = NULL,cur = head,next = cur->next;
下面进行头插:
cur->next = rhead,rhead = cur,cur = next,next = next->next
以上就是本题头插的核心步骤,下面是本题循环终止条件和bug点:
当cur指向空时,循环终止,但是当cur指向空时,也会出现next空指针的问题,在cur指向最后一个节点时,next就指向空了,所以这里我们也要对next进行一下判断。
代码实现:
struct ListNode* reverseList(struct ListNode* head)
{
if(head==NULL)
{
return NULL;
}
struct ListNode* rhead = NULL;
struct ListNode* cur = head;
struct ListNode* next = cur->next;
while(cur)
{
cur->next = rhead;
rhead = cur;
cur=next;
if(next)
{
next = next->next;
}
}
return rhead;
}
合并两个有序链表
链接: link
题目描述:
题目思路:带哨兵位解法
什么是带哨兵位?
带哨兵位就是在一条链表的前面,有一个空的节点不存放任何的值,如下图:
动态申请1个空间的哨兵位作为新的头,之后进行链接。
1、如果List1的值比List2的值小,那么head->next就是我们合并后链表新的头,之后让List1指向下一个节点,并且tail指向刚刚被插入的节点。
与此同时如果List2的值比List1的值小,那么head->next就是我们合并后链表新的头,之后让List2指向下一个节点,并且tail指向刚刚被插入的节点。
2、有了新链表的头之后,剩下的步骤就是比较两个节点的大小,那个节点值大,就将哪个节点拿下来尾插,并且让尾指针tail指向该尾插的节点。
3、在进行不断的尾插的过程中肯定会有一条链表为空,如果是List1为空,那么直接让tail->next链接List2,否则链接List1。
注意:
1、我们还要注意一点就是,很有可能给我们的两条链表有一条是空链表,此时只需要返回那条不为空的链表就好。
2、动态申请的两个节点最后要记得释放
代码实现:
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
if(list1==NULL)
{
return list2;
}
if(list2==NULL)
{
return list1;
}
if(list1==NULL&&list2==NULL)
{
return NULL;
}
struct ListNode* head = NULL;
struct ListNode* tail = NULL;
head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
while(list1&&list2)
{
if(list1->val<list2->val)
{
tail->next = list1;
tail=tail->next;
list1= list1->next;
}
else
{
tail->next = list2;
tail=tail->next;
list2= list2->next;
}
}
if(list1)
{
tail->next = list1;
}
if(list2)
{
tail->next = list2;
}
struct ListNode* del = head;
head = head->next;
free(del);
return head;
}
链表分割
链接: link
题目描述:
题目思路:
假设给定一串链表:
假设x的值我们设置为3,则分割链接后就是下面的结果:
本题思路依然是构造两个带有哨兵位的链表,将小于3的拿下来尾插到链表1,将大于3的拿下来尾插到链表2,最后将链表2链接到链表1的后面,返回链表1的头,同时释放两个哨兵位节点。
注意:第二个链表的尾指针最后要置空,否则链表中会出现环。
代码实现:
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
struct ListNode* lesshead,*lesstail,*greaterhead,*greatertail;
lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));
greaterhead = greatertail = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* cur = pHead;
while(cur)
{
if(cur->val<x)
{
lesstail->next = cur;
lesstail = lesstail->next;
}
else
{
greatertail->next = cur;
greatertail= greatertail->next;
}
cur=cur->next;
}
lesstail->next = greaterhead->next;
greatertail->next = NULL;
pHead = lesshead->next;
free(lesshead);
free(greaterhead);
return pHead;
}
};