您现在的位置是:首页 >技术教程 >数据结构之单链表oJ练习网站首页技术教程
数据结构之单链表oJ练习
目录
1.移除单链表中与给数相同的元素
解题思路:
初始化一个新链表,从头结点开始遍历,若相同,保存下一节点位置,再free 掉该节点,若不同将节点赋值给新链表。
代码段:
struct ListNode* removeElements(struct ListNode* head, int val) {
if(head == NULL)
return NULL;
struct ListNode* cur = head;
struct ListNode* prev = NULL;
while(cur)
{
//如果当前节点是需要删除的节点
if(cur->val == val)
{
//首先保存下一个节点
struct ListNode* next = cur->next;
//如果删除的为头节点,更新头节点
//否则让当前节点的前趋节点链接next节点
if(prev == NULL)
{
head = cur->next;
}
else
{
prev->next = cur->next;
}
//释放当前节点,让cur指向next
free(cur);
cur = next;
}
else
{
//如果cur不是需要删除的节点,则更新prev,cur
prev = cur;
cur = cur->next;
}
}
return head;
}
2.反转链表
解题思路:
1.链表逆置,将两个相邻的节点交换位置,交换n-1次,完成链表逆置。
代码段:
struct ListNode* reverseList(struct ListNode* head) {
if(head == NULL || head->next == NULL)
return head;
struct ListNode* n1, *n2, *n3;
n1 = head;
n2 = n1->next;
n3 = n2->next;
n1->next = NULL;
//中间节点不为空,继续修改指向
while(n2)
{
//中间节点指向反转
n2->next = n1;
//更新三个连续的节点
n1 = n2;
n2 = n3;
if(n3)
n3 = n3->next;
}
//返回新的头
return n1;
}
2.头插法,从第一个节点开始遍历,作为新链表的尾节点,然后每遍历一个,头插该节点在新链表中。
// 取节点头插的思想完成逆置
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;
}
3.找中间节点
解题思路:
快慢指针:给一个快指针与慢指针都是从链表的头节点开始遍历,快指针每次遍历两个节点,慢指针每次遍历一个节点,当快指针遍历结束时,慢指针刚好处于节点,返回慢指针。
这里需要考虑一下节点总数对于奇偶情况,若为奇数节点快指针刚好为NULL时,慢指针为中间。若为偶指针,则快指针的next为空时,慢指针为中间指针。
所以循环条件为两个都不为零时,即其中一个为零就是中间指针。
truct ListNode* middleNode(struct ListNode* head){
struct ListNode* faster=head;
struct ListNode* fast=head;
while(faster &&faster->next)
{
fast=fast->next;
faster=faster->next->next;
}
return fast;
}
4.找倒数第k个
解题思路:
与找中间节点的思路相同,当快指针指向第k个节点时,慢指针指向第一个节点,开始遍历,当快指针为NULL时,慢指针为该链表中倒数第k个节点。
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
// write code here
struct ListNode* fast=pListHead;
struct ListNode* slow =pListHead;
while(k--)
{
if(fast==NULL)
{
return NULL;
}
fast=fast->next;
}
while(fast)
{
fast=fast->next;
slow=slow->next;
}
return slow;
}
5.合并两个有序链表
解题思路:
尾插法:因为是有序链表,我们直接从前开始比较:给定两个指针分别指向链表一与链表二,这里返回的时第三个新链表,则让第一个指针指向节点的数与第二个指针指向节点的数作比较,谁小谁先插,将较小的那个数的节点尾插在链表三之后,之后第一个指针与第二个指针同时继续往后遍历,等到其中一个先遍历完的时候,将另一个指针指向的节点直接尾插到链表三中。若某一链表为空,则返回另外一个。
struct ListNode* mergeTwoLists(struct ListNode*list1, struct ListNode* list2){
struct ListNode*p1=list1;
struct ListNode*p2=list2;
if(p1 == NULL)
return p2;
else if(p2 == NULL)
return p1;
struct ListNode* head = NULL, *tail = NULL;
//创建空链表
head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
tail->next = NULL;
while(p1 && p2)
{
// 取小的进行尾插
if(p1->val < p2->val)
{
tail->next = p1;
tail = tail->next;
p1 = p1->next;
}
else
{
tail->next = p2;
tail = tail->next;
p2 = p2->next;
}
}
//剩余元素直接拼接
if(p1)
tail->next = p1;
else
tail->next = p2;
struct ListNode* list = head->next;
free(head);
return list;
}
6.链表分割
解题思路:
创建新链表时为了避免头节点判空这一繁琐的步骤,我们创建两个带哨兵位的链表,从已知链表头节点开始遍历,将小于x的该节点重新放在一个链表内,其余大于等于x按原顺序放在另一个链表内,之后free掉哨兵位,合并两个链表,尾节点置空,返回新头节点。
if(pHead == NULL)
return NULL;
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)
{
//小于x的尾插到lessTail
if(cur->val < x)
{
lessTail->next = cur;
lessTail = lessTail->next;
}
//大于等于x的尾插到greaterTail
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;
}
7.链表的回文结构
解题思路:
所谓回文结构就是链表是否对称,因此我们首先需要找的中间节点,将中间节点前的存放在一个链表内,将中间节点包括在中间节点逆置后放在另一个链表中,两链表比对,若有其中一个不相等返回false,孙环结束后返回true。
对于链表奇偶情况时,无论奇偶带有中间节点的比较长,而逆置后与前半部分对比,要么刚好,要么提前结束,不影响对称性。
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
if (A == NULL || A->next == NULL)
return true;
ListNode* slow, *fast, *prev, *cur, *tmp;
slow = fast = A;
//找到中间节点
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
prev = NULL;
//后半部分逆置
cur = slow;
while (cur)
{
tmp = cur->next;
cur->next = prev;
prev = cur;
cur = tmp;
}
//逐点比对
while (A && prev)
{
if (A->val != prev->val)
return false;
A = A->next;
prev = prev->next;
}
return true;
}
};
8.找公共节点
解题思路:本题可直接暴力求解,分别计算出A B两链表的长度,它们的长度差作为较长那个链表便利的条件,即两链表同长度开始比较,若相等则是公共节点,注意这里相同的是结点的地址。
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode* pa=headA;
struct ListNode* pb=headB;
int m=0,n=0;
while(pa)
{
pa=pa->next;
m ++;
}
while(pb)
{
pb=pb->next;
n++;
}
int x=m-n;
struct ListNode* a=headA;
struct ListNode* b=headB;
if(x>0)
{
while(x--)
{
a=a->next;
}
while(a)
{
if(a==b)
{
return a;
}
a=a->next;
b=b->next;
}
}else if(x<0)
{
while(x++)
{
b=b->next;
}
while(b)
{
if(a==b)
{
return b;
}
a=a->next;
b=b->next;
}
}else if(x==0)
{
while(a)
{
if(a==b)
{
return a;
} a=a->next;
b=b->next;
}
}
return NULL;
}