链表基本操作(删除 反转 重排)

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);

}