链表中每一个用于存储数据的单元叫做 element 或者 node，每一个结点中都包含一个指向下一个结点的指针一般被称为 next link 或者 next pointer，剩余的元素一般为数据元素，一般被称为 data, information, value, cargo 或者 payload。链表的第一个元素被称为链表的 head。
ListNode *head; ListNode *tail; int size; public: /** Initialize your data structure here. */ MyLinkedList() { head = newListNode(0); tail = newListNode(0); head->next = tail; tail->next = nullptr; size = 0; }
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */ intget(int index){ if (index + 1 > size || index < 0) { return-1; } ListNode *dummy{ head->next }; while (index--) { dummy = dummy->next; } return dummy->val; }
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */ voidaddAtHead(int val){ head->val = val; ListNode *dummy = newListNode(0); dummy->next = head; head = dummy; ++size; }
/** Append a node of value val to the last element of the linked list. */ voidaddAtTail(int val){ tail->val = val; ListNode *dummy = newListNode(0); tail->next = dummy; tail = dummy; ++size; }
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */ voidaddAtIndex(int index, int val){ if (index == size) { addAtTail(val); return; } if (index > size || index < 0) { return; } ListNode *dummy{ head }; while (index--) { dummy = dummy->next; } ListNode *element = newListNode(val); element->next = dummy->next; dummy->next = element; ++size; }
/** Delete the index-th node in the linked list, if the index is valid. */ voiddeleteAtIndex(int index){ if (index + 1 > size || index < 0) { return; } ListNode *dummy{ head }; while (index--) { dummy = dummy->next; } ListNode *deleted = dummy->next; dummy->next = deleted->next; deleted->next = nullptr; delete deleted; --size; } };
classSolution { public: ListNode * reverseBetween(ListNode* head, int m, int n){ ListNode *prev{}, *current{}, *next{}, *dummy{ head }, *left{}; for (int i = 1; i <= n; ++i) { if (i > m) { current->next = prev; prev = current; current = next; next = current->next; } elseif (i == m) { current = dummy; next = current->next; } else { left = dummy; dummy = dummy->next; } } current->next = prev; dummy->next = next; if (left) { left->next = current; } if (m == 1) { return current; } return head; } };
classSolution { public: ListNode * reverseBetween(ListNode* head, int m, int n){ int size{ n - m + 1 }; int *nums = newint[size]; ListNode *dummy{ head }, *begin{}; for (int i = 1; i < m; ++i, dummy = dummy->next); begin = dummy; for (int i = 0; i < size; nums[i] = dummy->val, dummy = dummy->next, ++i); for (int i = n - m; i >= 0; begin->val = nums[i], begin = begin->next, --i); return head; } };
设需要逆置的区间为 [M,N] 则，算法的时间复杂度为 O(2N−M+2)
0x02 奇靠前偶靠后
这个是来源于一道 LeetCode 题目 328. Odd Even Linked List，此题要求你将下标为偶数的元素全部移动到链表的最后，而且要在源链表的物理结构上实现（in place），我的代码如下：
同样，来自一道 LeetCode 题目，19. Remove Nth Node From End of List，给定一个单链表和一个整数 N，删除从结尾算起的第 N 号元素，对于此题采用递归的方法来倒序遍历链表以找到从结尾算起的第 N 号元素之前的那一个，然后将其 next 删除即可，算法不难想，时间复杂度在 O(N)，运行效率超过 100% 的人，代码如下：
LNode *head; LNode *tail; int size; public: /** Initialize your data structure here. */ MyLinkedList() { size = 0; head = newLNode(0); tail = newLNode(0); head->next = tail; tail->prev = head; }
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */ intget(int index){ if (index < 0 || index >= size) { return-1; } LNode *dummy = head->next; while (index--) { dummy = dummy->next; } return dummy->data; }
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */ voidaddAtHead(int val){ head->data = val; LNode *dummy = newLNode(0); dummy->next = head; head->prev = dummy; head = dummy; ++size; }
/** Append a node of value val to the last element of the linked list. */ voidaddAtTail(int val){ tail->data = val; LNode *dummy = newLNode(0); dummy->prev = tail; tail->next = dummy; tail = dummy; ++size; }
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */ voidaddAtIndex(int index, int val){ if (index > size || index < 0) { return; } if (index == size) { addAtTail(val); return; } LNode *dummy = head; while (index--) { dummy = dummy->next; } LNode *inserted = newLNode(val); inserted->prev = dummy; inserted->next = dummy->next; dummy->next->prev = inserted; dummy->next = inserted; ++size; }
/** Delete the index-th node in the linked list, if the index is valid. */ voiddeleteAtIndex(int index){ if (index >= size || index < 0) { return; } LNode *dummy = head; while (index--) { dummy = dummy->next; } LNode *deleted = dummy->next; dummy->next = deleted->next; deleted->next->prev = dummy; delete deleted; --size; } };
支付宝
