day4
24. 两两交换链表中的节点
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if (head == nullptr || head->next == nullptr) return head;
ListNode *result = new ListNode();
ListNode *p = head; // 前一节点
ListNode *q = head->next; // 后一节点
ListNode *temp = result;
result->next = head;
while (q != nullptr) {
p->next = q->next;
q->next = p;
temp->next = q;
temp = p;
if (temp->next == nullptr || temp->next->next == nullptr) break;
p = temp->next;
q = p->next;
}
head = result->next;
delete result;
return head;
}
};
9.删除链表的倒数第N个节点
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode *result = new ListNode();
result->next = head;
ListNode *p = result;
ListNode *q = head;
while(n--) {
q = q->next;
}
while (q != nullptr) {
q = q->next;
p = p->next;
}
q = p->next;
p->next = q->next;
delete q;
q = result->next;
delete result;
return q;
}
};
面试题 02.07. 链表相交
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
int length(ListNode* L) {
ListNode *p = L;
int num = 0;
while(p != NULL) {
num++;
p = p->next;
}
return num;
}
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int lenA = length(headA);
int lenB = length(headB);
int subLen = 0;
ListNode *p = headA;
ListNode *q = headB;
if (lenA > lenB) {
subLen = lenA - lenB;
while(subLen--) p = p->next;
} else {
subLen = lenB - lenA;
while(subLen--) q = q->next;
}
while (q != NULL && p != NULL) {
if (q == p) return q;
q = q->next;
p = p->next;
}
return NULL;
}
};
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 *slow = head;
ListNode *fast = head;
while(fast != NULL && fast->next != NULL) {
fast = fast->next->next;
slow = slow->next;
if (fast == slow) { // 相遇有环
slow = head;
while(slow != fast) {
slow = slow->next;
fast = fast->next;
}
return fast;
}
}
return NULL;
}
标签:head,ListNode,val,int,随想录,next,链表,节点
From: https://www.cnblogs.com/masene/p/17051811.html