网站建设 拖欠尾款,wordpress交易排行榜,做网站需要哪些框架,湖北做网站平台哪家好链表解题技巧
额外的数据结构#xff08;哈希表#xff09;#xff1b;快慢指针#xff1b;虚拟头节点#xff1b;
判断链表是否回文
要求#xff1a;时间辅助度O(N)#xff0c;空间复杂度O(1)
方法1#xff1a;栈#xff08;不考虑空间复杂度#xff09;
遍历一…链表解题技巧
额外的数据结构哈希表快慢指针虚拟头节点
判断链表是否回文
要求时间辅助度O(N)空间复杂度O(1)
方法1栈不考虑空间复杂度
遍历一次链表将节点地址依次压栈再此遍历链表每遍历一个节点与栈顶元素比对相等则栈顶元素出栈。如果直到链表结束和栈空元素都相等则为回文中间只要有一个不相等返回false。
bool LinkedList::isPalindromeListWithStack(ListNode *head) {if (head nullptr) return false;if (head-next nullptr) return true;// push into stackstd::stackListNode* stk;ListNode *cur head;while (cur) {stk.push(cur);cur cur-next;}// pop out stack comparecur head;while (!stk.empty()) {if (cur-val ! stk.top()-val) return false;cur cur-next;stk.pop();}return true;
}方法2快慢指针 栈
相对于方法1节省一半的空间但时间复杂度和空间复杂度不变。
快慢指针快指针一次走两步慢指针一次走一步。第一次快指针遍历结束时慢指针应到达中间位置奇数时到达中间位置偶数时向上取整的位置记录当前慢指针的位置慢指针继续移动并依次将节点指针添加进栈依次出栈并重新遍历链表直至栈空遍历过程中出现不相同的情况则为false反之为true。
bool LinkedList::isPalindromeListWithStackAndTwoPoints(ListNode *head) {if (head nullptr) return false;if (head-next nullptr) return true;// find middle positionListNode *slow head;ListNode *fast head-next;while (fast ! nullptr fast-next ! nullptr) {slow slow-next;fast fast-next-next;}if (fast ! nullptr) slow slow-next; // even// push into stackstd::stackListNode* stk;while (slow ! nullptr) {stk.push(slow);slow slow-next;}// pop out stack comparewhile (!stk.empty()) {if (head-val ! stk.top()-val) return false;stk.pop();head head-next;}return true;
}Notes
特别注意奇数和偶数情况下的指针定位。
如果要满足奇数时到达中间位置偶数时向上取整的位置。我们应该在快指针遍历完之后判断是否为偶数可以通过快指针是否为nullptr判断然后偶数情况下慢指针先往后移动一步然后在开始遍历剩下部分入栈。
方法3快慢指针 反转后半链表
该方法时间复杂度仍为O(N)空间复杂度降低为O(1)。
快慢指针快指针一次走两步慢指针一次走一步。第一次快指针遍历结束时慢指针应到达中间位置奇数时到达中间位置偶数时向下取整的位置记录当前慢指针的位置记为mid从慢指针到末尾的位置反转并记录末尾的位置记为tail从两端开始遍历左边是从head右边从tail。奇数情况下都会遍历到mid偶数情况下当左边遍历到mid即遍历完成。 遍历过程中一旦出现不一样的值即false反之true。
bool LinkedList::isPalindromeListWithTwoPoints(ListNode *head) {if (head nullptr) return false;if (head-next nullptr) return true;// find middle positionListNode *slow head;ListNode *fast head-next;while (fast ! nullptr fast-next ! nullptr) {slow slow-next;fast fast-next-next;}ListNode *mid slow;// reversefast slow-next;ListNode *tail LinkedList::reverse(slow-next);fast-next mid;mid-next nullptr;// traverse comparebool flag true;slow head;fast tail;while (slow ! mid) {if (slow-val ! fast-val) {flag false;break;}slow slow-next;fast fast-next;}// odd : the same node// even : the last middle nodeif (slow-val ! fast-val) flag false;// reverse backLinkedList::reverse(tail);return flag;
}Notes
其中反转后半部分链表的函数即为上文的反转单链表算法。再返回之前需要把链表复原。
