链表问题

单链表反转

ListNode* reversenode(ListNode* p) { if (p == NULL || p->next == NULL) return p; ListNode* cur = p; ListNode* pre = NULL; ListNode* next = p->next; while (next) { cur->next = pre; pre = cur; cur = next; next = cur->next; } cur->next = pre; return cur; }

循环链表反转

void reverselist(ListNode* a) { ListNode* head = a; ListNode* pre = a; ListNode* cur = a->next; ListNode* next = cur->next; while (cur != head) { cur->next = pre; pre = cur; cur = next; next = cur->next; } cur->next = pre; }

反转链表中从m到n

ListNode *reversemn(ListNode* p, int m, int n) { if (p == NULL || p->next == NULL || m == n) return p; int t = n - m; ListNode* prehead = new ListNode(-1); prehead->next = p; ListNode* pre = prehead; while (m > 1) { pre = pre->next; m--; } //cur指向第m-1个节点 ListNode* dump = pre->next; pre->next = NULL; ListNode* cur = dump; while (t) { cur = cur->next; t--; } ListNode* next = cur->next; cur->next = NULL; ListNode* newd=reversenode(dump); pre->next = newd; while (newd->next) newd = newd->next; newd->next = next; return prehead->next; }

链表按照奇数或偶数拆分

void chaifen(ListNode* head) { if (head == NULL || head->next == NULL) return; ListNode* p1 = head; ListNode* p2 = head->next; while ((p1&&p1->next) || (p2&&p2->next)) { if (p1 != NULL && p1->next != NULL){ p1->next = p1->next->next; p1 = p1->next; } if (p2 != NULL && p2->next != NULL) { p2->next = p2->next->next; p2 = p2->next; } } }

143 重排链表

先找到中间节点，然后把后半段反转，然后按照流程变换链表即可。（已收藏