登录/注册
fuyao-w
2359
占位
0
占位
0
浏览量
占位
粉丝
占位
关注
被火车撞了都不能忘记的几道题(你会了吗?)
fuyao-w
2022-07-05 15:05:27 2022-07-05
17
0

目录 一.删除有序链表中的重复元素I 二.删除有序链表重复元素II 三.环形单链表中插入一个元素 四.单链表翻转II 五.奇偶链表

一.删除有序链表中的重复元素I

1.对应牛客网链接:

删除有序链表中重复的元素-I_牛客题霸_牛客网 (nowcoder.com)

2.题目描述:

 3.解题思路

1.定义一个cur和next指针一开始cur指向头,next指针指向头的下一个 2.边遍历边比较 cur->val == next->val,若相等,则将 cur 就指向 next 的下一个节点,否则继续遍历,直至遍历完整个链表。

下面以1->2->3->3->4为例:

由于 cur 指向的节点的值(1)不等于 next 指向的节点的值(2),两个指针右移

不相等继续后移

相等,cur 指向 next 的下一节点(相当于删除链表中的重复元素 3),next 指针右移

直到next为空

4.对应代码

class Solution {

public:
/**
*
* @param head ListNode类
* @return ListNode类
/
ListNode
deleteDuplicates(ListNode* head) {
// write code here

    if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* cur = head;
ListNode* next = head->next;
while (next) {
if (cur->val == next->val) { //重复
while (next && next->val == next->val) {
ListNode* next = cur->next; //保存下一个节点
delete cur;
cur = next;
}
cur->next = next;
} else {
//指针一起移动
cur = next;
next = next->next;
}
}
return head;
}

};

递归版本:

class Solution {

public:
/**
*
* @param head ListNode类
* @return ListNode类
/
ListNode
deleteDuplicates(ListNode* head) {
// write code here
if (!head || !head->next) {
return head;
}
ListNode* next = head->next;
if (head->val != next->val) {
head->next = deleteDuplicates(head->next);
return head;
} else {
while (next && next->val == head->val) {
head->next = next->next;
delete next;
next = head->next;
}
head->next = deleteDuplicates(head->next);
return head;
}
}
};

二.删除有序链表重复元素II

1.对应牛客网链接:

删除有序链表中重复的元素-II_牛客题霸_牛客网 (nowcoder.com)

2.题目描述:

 3.解题思路

1.定义一个三个指针变量:last 、prev、cur一开始分别指针空、头节点和头节点的下一个 2.迭代变量如果prev的值和cur的值相等那么一直移动cur直到cur的值和prev不相等。如果prev的值和cur不相等则三个指针一起移动。直到cur为空

下面我们以1->3->3->4->4->5为例:

初始状态:

 发现prev和cur的值不相等三个指针一起移动

 此时prev和cur的值一样我们进行删除:

删除完成之后我们发现prev和cur的值又相等了继续进行删除

直到cur走到空结束循环将头节点返回即可

注意:(如果一开始就是头删需要进行特判改变头节点) 

4.对应代码

class Solution {

public:
/**
*
* @param head ListNode类
* @return ListNode类
/
ListNode
deleteDuplicates(ListNode* head) {
// write code here
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* prev = head;
ListNode* cur = head->next;
ListNode* last = nullptr;
while (cur) {
if (cur->val == prev->val) {
while (cur && cur->val == prev->val) {//进行删除
ListNode* next = cur->next;
delete cur;
cur = next;
}
delete prev;
prev = cur;
cur = cur ? cur->next : nullptr;
if (last == nullptr) {//特判头删的情况
head = prev;
} else {
last->next = prev;

            }
} else {//三个指针迭代走
last = prev;
prev = cur;
cur = cur->next;
}
}
return head;
}

};

递归版本:

class Solution {

public:
/**
*
* @param head ListNode类
* @return ListNode类
/
ListNode
deleteDuplicates(ListNode* head) {
// write code here
if (head == nullptr || head->next == nullptr) {
return head;
}

    if (head->val != head->next->val) {
head->next = deleteDuplicates(head->next);
return head;
} else {
//说明相等
int val = head->val;
while (val == head->val) {
ListNode* next = head->next;
delete head;
head = next;
if (head == nullptr)
return nullptr;
}
return deleteDuplicates(head);
}
}

};

三.环形单链表中插入一个元素

1.对应letecode链接:

剑指 Offer II 029. 排序的循环链表 - 力扣(LeetCode)

2.题目描述:

3.解题思路:

插入情况一:链表为空创建一个节点让自己指向自己 插入情况二:单链表只有一个节点或单链表中所有节点的值都相等 插入情况三:找到一个插入位置使其前节点值比Insertval小,后节点值比其Insertval大 情况四:当插入节点为最小值或者最大值

4.对应代码:

class Solution {

public:
Node* insert(Node* head, int insertVal) {
if (head == NULL) {
Node* newNode = new Node(insertVal);
newNode->next = newNode;
return newNode;
}
Node* cur = head;
while (1) {
if (cur->next ==
head) { //说明可能只有一个节点或者全是一种值的节点
break;
} else if (cur->val <= insertVal && cur->next->val >= insertVal) {
break;
} else if (cur->val > cur->next->val && (insertVal >= cur->val ||
insertVal <= cur->next->val)) {
break;
}
cur = cur->next;
}
cur->next = new Node(insertVal, cur->next);
return head;

}

};

四.单链表翻转II

1.对应牛客网链接

链表内指定区间反转_牛客题霸_牛客网 (nowcoder.com)

2.题目描述:

3.解题思路:

1.指向 left左边元素的指针 pre ,它表示未翻转的链表,需要把当前要翻转的链表结点放到 pre 之后。 cur 指向当前要翻转的链表结点。 nxt 指向 cur.next ,表示下一个要被翻转的链表结点。 tail 指向已经翻转的链表的结尾,用它来把已翻转的链表和剩余链表进行拼接

 4.对应代码:

/**

  • struct ListNode {
  • int val;
  • struct ListNode *next;
  • };
  • /

class Solution {

public:
/**
*
* @param head ListNode类
* @param m int整型
* @param n int整型
* @return ListNode类
/
ListNode
temp=nullptr;
ListNode* reverseBetween(ListNode* head, int m, int n) {
// write code here
if(m==1)
{
return ReversN(head, n);
}
ListNodenode=reverseBetween(head->next, m-1, n-1);
head->next=node;
return head;
}
ListNode
ReversN(ListNodehead,int n)
{
if(n==1)
{
temp=head->next;//保存后面的节点
return head;
}
ListNode
node=ReversN(head->next,n-1);
//开始翻转
head->next->next=head;
head->next=temp;
return node;

}

};

递归版本:

1.如果m ==1,就相当于反转链表的前n元素。 2.如果m != 1我们把 head的索引视为1,那么我们是想从第m个元素开始反转,如果扎head.next的索引视为1,那相对于head.next,反转的区间3.应该是从第m-1个元素始的,以此类推,递归拼接后续已反转的链表。 对于每次反转,如果n等于1,相当于只颠倒第一个节点,如果不是,则进入后续节点问题),将后续反转的内容接到前面即可。

对应代码

/**

  • struct ListNode {
  • int val;
  • struct ListNode *next;
  • };
  • /

class Solution {

public:
/**
*
* @param head ListNode类
* @param m int整型
* @param n int整型
* @return ListNode类
/
ListNode
temp=nullptr;
ListNode* reverseBetween(ListNode* head, int m, int n) {
// write code here
if(m==1)
{
return ReversN(head, n);
}
ListNodenode=reverseBetween(head->next, m-1, n-1);
head->next=node;
return head;
}
ListNode
ReversN(ListNodehead,int n)
{
if(n==1)
{
temp=head->next;//保存后面的节点
return head;
}
ListNode
node=ReversN(head->next,n-1);
//开始翻转
head->next->next=head;
head->next=temp;
return node;

}

};

五.奇偶链表

1.对应letecode链接:

  1. 奇偶链表 - 力扣(LeetCode)

2.题目描述:

 3.解题思路:

1.根据节点编号的奇偶性,我们可以将奇数节点和偶数节点分离成奇数链表和偶数链表,然后将偶数链表连接在奇数链表之后,合并后的链表即为结果链表。 2、从前往后遍历整个链表,遍历时维护四个指针:奇数链表头结点,奇数链表尾节点,偶数链表头结点,偶数链表尾节点,遍历时将位置编号是奇数的节点插在奇数链表尾节点后面,将位置编号是偶数的节点插在偶数链表尾节点后面。

4.对应代码:

class Solution {

public:
ListNode* oddEvenList(ListNode* head) {
if (head == nullptr) {
return nullptr;
}
ListNode* oddList = head;
ListNode* EeveList = head->next;
ListNode* oddcur = oddList;
ListNode* evercur = EeveList;
ListNode* cur = head;
while (evercur && evercur->next) {//链表长度有可能是奇数或者是偶数
oddcur->next = evercur->next;
oddcur = oddcur->next;
evercur->next = oddcur->next;
evercur = evercur->next;
}
oddcur->next = EeveList;//链接
return head;

}

};

 

暂无评论