1)删除某个链表中给定的(非尾)结点
struct ListNode* doDeleteNode(struct ListNode* head, int val){
struct ListNode *pre, *now;
if(head == NULL) {
return NULL;
}
if(head->val == val) {
return head->next;
}
pre = head, now = head->next;
while(now) {
if(now->val == val) {
pre->next = now->next;
break;
}
pre = now;
now = now->next;
}
return head;
}
void deleteNode(struct ListNode* node){
int tmp = node->val;
node->val = node->next->val;
node->next->val = tmp;
doDeleteNode(node, tmp);
}
2)给定单链表的头结点,要求反转链表
class Solution {
ListNode *removeNextAndReturn(ListNode* now) {
if(now == nullptr || now->next == nullptr) {
return nullptr;
}
ListNode *retNode = now->next;
now->next = now->next->next;
return retNode;
}
public:
ListNode* reverseList(ListNode* head) {
ListNode *doRemoveNode = head;
while(doRemoveNode) {
ListNode *newHead = removeNextAndReturn(doRemoveNode);
if(newHead) {
newHead->next = head;
head = newHead;
}else {
break;
}
}
return head;
}
};
3)给定一个头结点的非空单链表,返回链表的中间结点,如果有两个中间结点,则返回第二个中间结点
class Solution {
public:
int listCount(ListNode *head) {
ListNode *now = head;
int cnt = 0;
while(now) {
now = now->next;
++cnt;
}
return cnt;
}
ListNode* middleNode(ListNode* head) {
int cnt = listCount(head) / 2;
while(cnt--) {
head = head->next;
}
return head;
}
};
4)给你一个链表,删除链表的倒数第n个结点,并且返回链表的头结点
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
vector <ListNode*> nodes;
ListNode *now = head;
while(now) {
nodes.push_back(now);
now = now->next;
}
if(n == nodes.size()) {
head = head->next;
}else {
ListNode *last = head;
for(int i = 1; i < nodes.size(); ++i) {
if(i == nodes.size() - n) {
continue;
}
last->next = nodes[i];
last = nodes[i];
}
last->next = NULL;
}
return head;
}
};
5)反转链表(1234567-->1726354)
// 奇数： L1 -> L2 -> L3 返回 L2
// 偶数： L1 -> L2 返回 L2
struct ListNode* getHalf(struct ListNode* head) {
struct ListNode *prev, *slow, *fast, *half;
if(head == NULL) {
return head;
}
prev = NULL;
slow = head;
fast = head;
while(fast && fast->next) {
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
half = slow;
if(prev)
prev->next = NULL;
return half;
}
struct ListNode *removeNextAndReturn(struct ListNode* now) { // (1)
struct ListNode *retNode;
if(now == NULL || now->next == NULL) {
return NULL;
}
retNode = now->next;
now->next = now->next->next;
return retNode;
}
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode *newHead;
struct ListNode *doRemoveNode = head;
while(doRemoveNode) {
newHead = removeNextAndReturn(doRemoveNode);
if(newHead) {
newHead->next = head;
head = newHead;
}else {
break;
}
}
return head;
}
struct ListNode* merge(struct ListNode* a, struct ListNode* b) {
struct ListNode* tmp;
if(a == NULL) {
return b;
}
tmp = a->next;
a->next = b;
b->next = merge(tmp, b->next);
return a;
}
void reorderList(struct ListNode* head){
struct ListNode* half = getHalf(head);
if(head == half)
return head;
half = reverseList(half);
merge(head, half);
}