您现在的位置是:首页 >学无止境 >LeetCode 链表OJ分享网站首页学无止境
LeetCode 链表OJ分享
删除排序链表中的重复元素
链接: link
题目描述:
题目思路:
本题思路使用双指针,以示例二为例如下图:
如果head->val等于next->val,那么此时就要删除重复节点next,具体步骤:
1、创建一个节点指针del记录被删除的节点next
2、next指针向下移动
3、free(del)
4、链接cur和next,cur->next=next
如果head->val不等于next->val,那么此时就要向下移动节点指针,具体步骤:
cur=next;
next=next->next
循环结束条件:当next指针指向空时,循环结束,返回链表的头
本题注意两点:
1、注意链表只有一个节点时,不做删除重复元素的操作,直接返回链表的头。
2、注意如果该链表为空链表,直接返回NULL。
代码实现:
struct ListNode* deleteDuplicates(struct ListNode* head)
{
if(head==NULL)
{
return NULL;
}
if((head->next)==NULL)
{
return head;
}
struct ListNode* cur = head;
struct ListNode* next = cur->next;
while(next)
{
if(cur->val==next->val)
{
struct ListNode* del = next;
next = next->next;
cur->next = next;
free(del);
}
else
{
cur=cur->next;
next = next->next;
}
}
return head;
}
回文链表
链接: link
题目描述:
题目思路:
本题主要核心步骤分为两三大步,第一步就是寻找中间节点,第二步逆置中间节点后的其他节点,第三步分别从头节点和中间节点开始,对比元素是否相等,如果相等为回文链表返回true,不相等返回false。
第一步:寻找中间节点
思路:快慢指针,快指针一次走两步,慢指针一次走一步
偶数节点循环结束条件分析:
循环结束条件为fast=NULL
奇数节点循环结束条件分析:
循环结束条件为fast->next=NULL
第一步代码实现:
struct ListNode* MiddleNode(struct ListNode* head)
{
struct ListNode* slow = head;
struct ListNode* fast = head;
while(fast&&fast->next)
{
slow=slow->next;
fast = fast->next->next;
}
return slow;
}
第二步:逆置中间节点后的节点
思路:改变链表指向,返回逆置后链表新的头
1、三个指针n1 n2 n3,逆置以下图为例
改变n2的指向,n2->next=n1
3个指针同时后移:n1=n2 n2=n3 n3=n3->next
循环上述步骤操作
循环结束条件分析:
本题循环结束条件为n2为空,但是n2为空的同时还要注意n3指针的空指针问题,如下图,n1到达最后一个节点,此时n2刚好为空,但是n3在上述迭代的情况下,下图的位置显然是不正确的。
此处应该注意加以判断n3是否为空,如果n3为空,则不再进行向下移动的迭代,最后返回n1,即为逆置后链表新的头。
第二步代码实现:
struct ListNode* reverseNode(struct ListNode* mid)
{
struct ListNode* n1 = NULL;
struct ListNode* n2 = mid;
struct ListNode* n3 = mid->next;
while(n2)
{
n2->next = n1;
//迭代
n1=n2;
n2=n3;
if(n3)
{
n3=n3->next;
}
}
return n1;
}
第三步分别从头节点和中间节点开始,对比元素是否相等,如果相等为回文链表返回true,不相等返回false。
经过上述两个步骤的修改后,链表的形态如下图:
对比元素是否相等,循环结束条件:rmid!=NULL
代码实现:
struct ListNode* MiddleNode(struct ListNode* head)
{
struct ListNode* slow = head;
struct ListNode* fast = head;
while(fast&&fast->next)
{
slow=slow->next;
fast = fast->next->next;
}
return slow;
}
struct ListNode* reverseNode(struct ListNode* mid)
{
struct ListNode* n1 = NULL;
struct ListNode* n2 = mid;
struct ListNode* n3 = mid->next;
while(n2)
{
n2->next = n1;
//迭代
n1=n2;
n2=n3;
if(n3)
{
n3=n3->next;
}
}
return n1;
}
bool isPalindrome(struct ListNode* head)
{
struct ListNode* mid = MiddleNode(head);
struct ListNode* rmid = reverseNode(mid);
struct ListNode* cur = head;
while(rmid)
{
if(cur->val==rmid->val)
{
cur=cur->next;
rmid=rmid->next;
}
else
{
return false;
}
}
return true;
}
剑指Offer 06.从尾到头打印链表
链接: link
题目描述:
题目思路:
思路同上题: 1、逆置链表,改变链接方向
2、求出链表节点的个数returnSize
3、动态开辟数组,数组元素个数为returnSize
4、释放动态开辟的内存空间
代码实现:
int countList(struct ListNode* head)
{
int count=0;
struct ListNode* cur = head;
while(cur)
{
count++;
cur=cur->next;
}
return count;
}
struct ListNode* reverseList(struct ListNode* head)
{
if(head==NULL)
{
return NULL;
}
if(head->next==NULL)
{
return head;
}
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->next;
}
}
return n1;
}
int* reversePrint(struct ListNode* head, int* returnSize)
{
int ret = countList(head);
*returnSize = ret;
struct ListNode* newhead = reverseList(head);
int * tmp = (int*)malloc(sizeof(int)*(*returnSize));
if(tmp==NULL)
{
perror("malloc fail");
return NULL;
}
struct ListNode* cur = newhead;
int i = 0;
while(i<ret&&cur)
{
tmp[i]=cur->val;
cur=cur->next;
i++;
}
return tmp;
free(tmp);
tmp=NULL;
}
复制带随机指针的链表
链接: link
题目描述:
题目思路:
1、拷贝节点插入到原节点后面
步骤:
1、画图明确拷贝节点和原节点
2、动态开辟一个内存空间存放拷贝节点
struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
将原节点的值赋值给拷贝节点 copy->val=cur->val
3、链接拷贝节点
4、循环条件:cur!=NULL,循环进行上述步骤
2、控制拷贝节点的random:copy->random=cur->random->next;
步骤:
1、此时copy节点就在cur节点的后面,cur->next = copy
2、如果cur原节点的random为空,那么拷贝节点的random也为空
3、如果原节点的random不为空,拷贝节点的random和原节点的random相等,copy->random=cur->random->next;拷贝节点的random在原节点random的下一个节点。
4、迭代向下,cur=copy->next
3、拷贝节点从原链表上解下来尾插形成新的链表,并且恢复原链表(具体看图实现)
步骤:
1、将拷贝节点尾插到新的链表
2、恢复原链表(依次按原链表链接)
struct Node* copyRandomList(struct Node* head)
{
//1、将拷贝节点链接到原节点的后面
struct Node* cur = head;
while(cur)
{
struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
copy->val=cur->val;
//链接
struct Node* next = cur->next;
cur->next = copy;
copy->next = next;
cur=next;
}
//2、控制拷贝节点的random
cur = head;
while(cur)
{
struct Node* copy = cur->next;
if(cur->random==NULL)
{
copy->random=NULL;
}
else
{
copy->random=cur->random->next;
}
cur=copy->next;
}
//3、尾插新链表,恢复原链表
cur = head;
struct Node* copyHead = NULL,* copyTail = NULL;
while(cur)
{
struct Node* copy = cur->next;
struct Node* next = copy->next;
if(copyHead==NULL)
{
copyHead = copyTail=copy;
}
else
{
copyTail->next = copy;
copyTail=copyTail->next;
}
//恢复原链表
cur->next = next;
cur= next;
}
return copyHead;
}