day4
24.两两交换链表中的节点
题目链接：24.两两交换链表中的节点
解题思路：使用虚拟头结点，具体步骤如下图
// 代码，包括从数组转换为链表的代码，acm模式
#include <iostream>
#include <vector>
using namespace std;
//定义链表结构体
struct ListNode {
int val; //链表的值
ListNode* next; //下一个指针
ListNode(int x) : val(x), next(NULL) {} //构造函数
ListNode(int x,ListNode* next1):val(x),next(next1){}
};
class Solution {
public:
//生成单链表
ListNode* createList(int* arr, int n) {
ListNode* head = new ListNode(*arr);
arr++;
ListNode* pre = head;
for (int i = 0; i < n - 1; ++i) {
ListNode* next = new ListNode(*arr);
pre->next = next;
arr++;
pre = pre->next;
}
return head;
}
ListNode* createList1(vector<int>& vec) {
ListNode* head = new ListNode(vec[0]);
ListNode* pre = head;
for (int i = 1; i < vec.size(); i++) {
ListNode* tmp = new ListNode(vec[i]);
pre->next = tmp;
pre = tmp;
}
return head;
}
ListNode* swapPairs(ListNode* head) {
//定义虚拟头节点
ListNode* dummyhead = new ListNode(0,head);
//dummyhead->next = head;
ListNode* cur = dummyhead;
//确定终止条件
while (cur->next != NULL && cur->next->next != NULL) {
ListNode* tmp = cur->next; //1节点
ListNode* tmp1 = cur->next->next->next; //3节点
cur->next = cur->next->next; //cur指向2节点
cur->next->next = tmp; // 1节点
cur->next->next->next = tmp1; //3节点
cur = cur->next->next; //要交换节点的前一个节点
}
return dummyhead->next;
}
};
//主函数
int main() {
Solution solution;
vector<int> vec = { 1,2,3,4 };
int a[] = {1,2,3,4};
ListNode* head = solution.createList1(vec);
head = solution.swapPairs(head);
ListNode* cur = head;
while (cur != NULL) {
cout << cur->val << " ";
cur = cur->next;
}
cout << endl;
//int a[3][3] = {
// {1,2,3},
// {4,5,6},
// {7,8,9},
//};
//cout << **(*&a + 1) << " ";
//cout << **(a + 1) << " ";
//cout << **a << " ";
//cout << endl;
return 0;
}
19.删除链表的倒数第N个节点
题目链接：19. 删除链表的倒数第 N 个结点
要删除链表的倒数第n个节点，使用双指针的方法，定义快慢指针，让快指针先走n+1步，这里+1是为了让slow定位到删除节点的前一个节点，最后c++中需要释放内存。
#include <iostream>
#include <vector>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
ListNode(int x, ListNode* next) :val(x), next(next) {}
};
class Solution {
public:
ListNode* deleteNthFromEnd(ListNode* head, int n) {
//定义虚拟节点
ListNode* dummyHead = new ListNode(0, head);
//定义快慢指针
ListNode* slow = dummyHead;
ListNode* fast = dummyHead;
// 让fast先走N+1步，因为要删除第N个因此slow需要定位到n前面哪一个
n++;
while (n-- && fast != NULL) {
fast = fast->next;
}
//两个指针同时往前走
while (fast != NULL) {
fast = fast->next;
slow = slow->next;
}
//清除内存
ListNode* tmp = slow->next;
slow->next = slow->next->next;
delete tmp;
return dummyHead->next;
}
//数组转为链表
ListNode* CreateList(vector<int>& vec) {
ListNode* head = new ListNode(vec[0]);
ListNode* pre = head;
for (int i = 1; i < vec.size(); i++) {
ListNode* tmp = new ListNode(vec[i]);
pre->next = tmp;
pre = tmp;
}
return head;
}
};
//主函数
int main() {
Solution solution;
vector<int> test = { 1,2,3,4,5 };
int n = 2;
ListNode* head = solution.CreateList(test);
head = solution.deleteNthFromEnd(head, n);
ListNode* cur = head;
while (cur != NULL) {
cout << cur->val << " ";
cur = cur->next;
}
cout << endl;
return 0;
}
面试题02.07.链表相交
题目链接：面试题 02.07. 链表相交
解题思路：参考
本题有两种思路
- 两层for循环遍历
- 使用双指针，不过之前需要先进行对齐，向后对其。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
// //定义两个指针
// ListNode* dummyHeadA = new ListNode(0);
// ListNode* dummyHeadB = new ListNode(0);
// dummyHeadA->next = headA;
// dummyHeadB->next = headB;
// ListNode* curA = dummyHeadA->next;
// ListNode* curB = dummyHeadB->next;
// while( curA != NULL){
// while( curB != NULL){
// if ( curB == curA){
// return curB;
// }
// curB = curB->next;
// }
// curA = curA->next;
// curB = dummyHeadB;
// }
// return NULL;
// 双指针，求出两个链表的长度
ListNode* curA = headA;
ListNode* curB = headB;
int lenA = 0, lenB = 0;
while( curA != NULL ){
lenA++;
curA = curA->next;
}
while( curB != NULL ){
lenB++;
curB = curB->next;
}
curB = headB;
curA = headA;
// 长度差
int error = abs(lenA - lenB);
//判断哪个链表更长
while( error--){
if( lenA > lenB){
curA = curA->next;
}
else if( lenA < lenB){
curB = curB->next;
}
}
//开始判断链表是否相等
while( curA != NULL){
if( curA == curB ) return curA;
curA = curA->next;
curB = curB->next;
}
return NULL;
}
};
142.环形链表II
题目链接：142. 环形链表 II
还是使用快慢指针
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
// 定义快慢指针
ListNode* fast = head;
ListNode* slow = head;
//进入循环
while( fast != NULL && fast->next != NULL){
fast = fast->next->next;
slow = slow->next;
if ( slow == fast){
ListNode* index1 = fast;
ListNode* index2 = head;
while( index1 != index2){
index1 = index1->next;
index2 = index2->next;
}
return index1;
}
}
return NULL;
}
};