707.设计链表
题目
题意：
在链表类中实现这些功能：
- get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
- addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
- addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
- addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
- deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
示例：
MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3
linkedList.get(1); //返回2
linkedList.deleteAtIndex(1); //现在链表是1-> 3
linkedList.get(1); //返回3
思路（链表的题目尽量都用虚拟头结点）
主要就是应用虚拟头结点对链表进行操作，这个题主要是让大家熟悉链表结点的结构体，以及怎么去初始化，怎么删除添加元素，因为在面试的时候这些结构体是需要我们自己去定义的。
整体代码如下
class MyLinkedList {
public:
/** Initialize your data structure here. */
struct ListNode {
int val;//链表结点结构体
ListNode* next;
ListNode(int val):val(val), next(nullptr){}
};
MyLinkedList() {
headnode=new ListNode(0);//创建虚拟头结点
List_size=0;
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
int get(int index) {
if(index>List_size-1||index<0)
{
return -1;
}
ListNode *p;
p=headnode;
for(int i=0;i<=index;i++)
{
p=p->next;
}
return p->val;
}
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
void addAtHead(int val) {
ListNode* s=new ListNode(val);
s->next=headnode->next;
headnode->next=s;
List_size++;
}
/** Append a node of value val to the last element of the linked list. */
void addAtTail(int val) {
ListNode* p;
p=headnode;
ListNode* s=new ListNode(val);
while(p->next!=nullptr)
{
p=p->next;
}
p->next=s;
List_size++;
}
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
void addAtIndex(int index, int val) {
ListNode* p;
p=headnode;
if(index<=List_size-1&&index>=0)
{
for(int i=0;i<=index-1;i++)
{
p=p->next;
}
ListNode* s=new ListNode(val);
s->next=p->next;
p->next=s;
List_size++;
}
else if(index<0)
{
ListNode* s=new ListNode(val);
s->next=headnode->next;
headnode->next=s;
List_size++;
}
else if(index==List_size)
{
ListNode* s=new ListNode(val);
while(p->next!=NULL)
{
p=p->next;
}
p->next=s;
List_size++;
}
}
/** Delete the index-th node in the linked list, if the index is valid. */
void deleteAtIndex(int index) {
if(index>=0&&index<=List_size-1)
{
ListNode *p;
p=headnode;
for(int i=0;i<=index-1;i++)
{
p=p->next;
}
ListNode *s;
s=p->next;
p->next=p->next->next;
delete s;
List_size--;
}
}
int List_size;
ListNode* headnode;
};
203.移除链表元素
题目
题意：删除链表中等于给定值 val 的所有节点。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1
输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]
思路（链表的题目尽量都用虚拟头结点）
以示例1为粒子，删除元素6
也就是将元素2的指向直接指向3，并删除元素6所占用的地址
而链表删除的操作主要是分两类：
- 一类带有虚拟头结点进行删除（删除方法同情况2）
- 一类是不带虚拟头结点进行删除（这样需要主要所删除的元素时头结点，所以要分2中情况讨论）：
- 移除头结点和移除其他节点的操作是不一样的，因为链表的其他节点都是通过前一个节点来移除当前节点，而头结点没有前一个节点。所以头结点如何移除呢，其实只要将头结点向后移动一位就可以，这样就从链表中移除了一个头结点。
- 删除非头结点时直接将前一个节点的指向改为所删除节点的后一个结点，然后清空需要删除结点的地址
整体代码
带虚拟头结点
class Solution {
public:
ListNode* removeElements(ListNode* head, int val)
{
ListNode* headnode=new ListNode(51);//创建虚拟头结点
headnode->next=head;//将头结点与head连接起来
ListNode* p=headnode;
while(p->next!=NULL)//记得要保留前一节点
{
if(p->next->val!=val)
{
p=p->next;
}
else
{
ListNode* q;
q=p->next;
p->next=p->next->next;
delete q;
}
}
head=headnode->next;
delete headnode;
return head;
}
};
不带头结点
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
// 删除头结点
while (head != NULL && head->val == val) { // 注意这里不是if
ListNode* tmp = head;
head = head->next;
delete tmp;
}
// 删除非头结点
ListNode* cur = head;
while (cur != NULL && cur->next!= NULL) {
if (cur->next->val == val) {
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
} else {
cur = cur->next;
}
}
return head;
}
};
206.反转链表
题目
题意：反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
思路（链表的题目尽量都用虚拟头结点）
暴力解法：定义一个新的链表，然后将链表从头到尾放入栈中，在一次出栈，并用新链表连接起来，实现链表元素的反转，其实这是对内存空间的浪费。
双指针法：一个指针指向当前节点，一个指针指向前一个节点，只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表；
整体代码如下：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* p=head;//快指针指向当前节点
ListNode* pre=NULL;//慢指针指向前一个节点
while(p)
{
ListNode* temp;
temp=p->next;
p->next=pre;
pre=p;
p=temp;
}
return pre;
}
};
24. 两两交换链表中的节点
题目
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
思路（链表的题目尽量都用虚拟头结点）
该题同样也是双指针的思想，但是切记用虚拟头结点去链接链表，不然要额外处理头结点，其思想仍然是也就是交换两指针的指向，但是切记在交换后的结点，后一个结点要将他的指向与链表连接起来。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UBoEauby-1639058827854)(C:\Users\Tang\AppData\Roaming\Typora\typora-user-images\image-20211209172426172.png)]
整体代码如下
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* head_node=new ListNode(0);
head_node->next=head;
ListNode* p=head_node;
if(head==NULL||head->next==NULL) return head;
while(head_node->next!=NULL&&head_node->next->next!=NULL)
{
ListNode *cur=head_node->next->next;
ListNode *pre= head_node->next;
ListNode *aft=head_node->next->next->next;
head_node->next=cur;
head->next->next=pre;
head_node->next->next->next=aft;
head_node=head_node->next->next;
}
return p->next;
}
};
19.删除链表的倒数第N个节点
题目
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？
示例 1：
输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5] 示例 2：
输入：head = [1], n = 1 输出：[] 示例 3：
输入：head = [1,2], n = 1 输出：[1]
思路（链表的题目尽量都用虚拟头结点）
该题思路也是双指针的思想，一个为快指针用来遍历到末尾从而确定慢指针在同时遍历的情况下走到要删除结点的前一个节点；
也就是如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。
整体代码如下：
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* head_node = new ListNode(0);
head_node->next = head;
ListNode* slow = head_node;//慢指针找到目标节点的前一个节点
ListNode* fast = head_node;//遍历到末尾使得慢指针找到目标节点的前一个节点
while(n-- && fast != NULL) {
fast = fast->next;
}
fast = fast->next; // fast再提前走一步，因为需要让slow指向删除节点的上一个节点
while (fast != NULL) {
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
return head_node->next;
}
};
面试题 02.07. 链表相交
题目
给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。换句话说，如果一个链表的第k个节点与另一个链表的第j个节点是同一节点（引用完全相同），则这两个链表相交。
示例1：
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
思路
由题目可以知道我们要找到最开始相交的结点，我们要注意他们能相交不仅仅是该节点储存的数值是相等的，它们的指向也都是相同的；（如果两个单链表有共同的节点，那么从第一个共同节点开始，后面的节点都会重叠，直到链表结束。 因为两个链表中有一个共同节点，则这个节点里的指针域指向的下一个节点地址一样，所以下一个节点也会相交，依次类推）
所以我们可以遍历不同头结点的链表的长度；
然后让长的链表向后遍历直到当前长度与短链表的长度相等位置。然后在遍历看能否找到相交的位置；
整体代码如下
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{
ListNode *p=headA;
ListNode *q=headB;
int lengthA,lengthB;
lengthA=lengthB=0;
//遍历各自头结点的链表长度
while(p!=NULL)
{
lengthA++;
p=p->next;
}
while(q!=NULL)
{
lengthB++;
q=q->next;
}
//使长链表向后遍历使两链表长度相等
if(lengthA>=lengthB)
{
for(int i=0;i<lengthA-lengthB;i++)
{
headA=headA->next;
}
while(lengthB--)
{
if(headA==headB) return headA;
headA=headA->next;
headB=headB->next;
}
return NULL;
}
else
{
for(int i=0;i<lengthB-lengthA;i++)
{
headB=headB->next;
}
while(lengthA--)
{
if(headA==headB) return headA;
headA=headA->next;
headB=headB->next;
}
return NULL;
}
}
};