1、遍历链表得到链表的长度length；2、得到链表的长度是为了获取链表翻转的次数（length / k），循环翻转链表即可。时间复杂度：o(n)空间复杂度：o(1) class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { //特殊情况处理 if (k == 1 || head == nullptr || head->next == nullptr) return head; //设置表头 ListNode* res ...

只要能得到倒数第n个结点前一个结点，就能实现删除结点。该题的重点是如何得到倒数第n个结点的前置结点。方法一：1、遍历链表得到链表的长度length；2、倒数第n个结点即为正数第(length - n - 1)个结点，再遍历链表至第(length - n)结点，即可完成删除。可以发现对链表的操作，很多情况需要设置表头，这样是为了便于对头结点进行操作时间复杂度：o(n)空间复杂度：o(1) class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { //特殊情况处理 ...

运用双指针求解，快指针和慢指针，快指针一次移动两个结点，慢指针一次移动一个结点。1、如果链表中有环结构，先用双指针找到环内的结点；2、再将其中一个指针移动到头结点，两个结点同时每次移动一个结点，下次相遇时就是环的入口结点时间复杂度：o(n)空间复杂度：o(1) class Solution { public: ListNode* EntryNodeOfLoop(ListNode* pHead) { //特殊情况处理 if (pHead == nullptr || pHead->next == nullptr) retur...

先得到反转区间的开始结点pcur，得到结点pcur的前置结点pre（因为pcur结点可能为头结点，所以我们将pre结点初始化为指向头结点的结点 pre->next = head)。得到上述两个结点后，可以将问题转换为：将反转区间的结点一个个放入结点pre和结点pcur之间，注意结点pre和pcur是不变的，我们要做的只是将结点pcur->next放入pre和pcur之间。时间复杂度：o(n)空间复杂度：o(1) class Solution { public: ListNode* reverseBetween(ListNode* head, int m, int n) ...

删除单链表中的某个结点只需要将指针绕过它，指向它的下一个结点即可。从链表的头指针开始遍历，分为两种情况：1、当前指针（pnode）与下一个指针（pnode->next）的值不同，当前指针移动到下一个指针（pnode = pnode->next）；2、当前指针与下一个指针的值相同，则将当前指针指向它的下下个指针（pnode->next = pnode->next->next）。直到遍历完整个链表，就删除了链表中重复的元素。时间复杂度：o(n)空间复杂度：0(1) class Solution { public: ListNode* deleteDupli...

方法一：使用双指针、反转链表求解（推荐）如果一个链表为回文结构，则链表的前半段和后半段是对称的。1、利用两个指针（快指针、慢指针），快指针每次移动两个结点，慢指针每次移动一个结点，可以得到链表的中间结点；2、得到链表的中间结点，从中间结点开始将后续的链表进行反转；3、比较链表前半段和后半段的值是否对称。时间复杂度：o(n)空间复杂度：o(1) class Solution { public: //反转链表 ListNode* reverse(ListNode* phead) { ListNode* ptemp = nullptr; while...

利用双指针求解：1、先得到两个链表的长度；2、如果两个链表的长度不同，则将长度较长的链表先移动，使得两个链表剩余的结点数相同；3、两个链表再同时移动，如果两个链表有公共结点，移动过程中一定会相遇在第一个公共结点。时间复杂度：o(n)空间复杂度：o(1) class Solution { public: ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) { //特殊情况处理 if (pHead1 == nullptr || pHead2 == nullptr) ...

方法一：先遍历链表得到链表的节点数目，即可得到倒数最后K个节点是正数第几个节点。时间复杂度：o(n)空间复杂度：o(1) class Solution { public: ListNode* FindKthToTail(ListNode* pHead, int k) { //特殊情况处理；链表为空和k不大于0两种情况 if (pHead == nullptr || k <= 0) return nullptr; ListNode* pnode = pHead; ListNode* temp ...

使用双指针，如果链表中有环，那么一定没有指向nullptr的节点；设置两个指针，一个指针一次走一步，另一个指针一次走两步，如果链表有环，两个指针一定会相遇。时间复杂度：o(n)空间复杂度：o(1) class Solution { public: bool hasCycle(ListNode *head) { //特殊情况处理 if (head == nullptr) return false; ListNode* pslow = head; ListNode* pfast = h...

第一种方法：双指针迭代时间复杂度：o(n)空间复杂度：o(1) class Solution { public: ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { ListNode* phead = new ListNode(0); //用于生成新链表的头结点（phead->next），val为0 ListNode* cur = phead; //特殊情况处理 if (pHead1 == nullptr) return pHead2; ...

第一种方法：利用双指针迭代求解时间复杂度为：o(n)空间复杂度为：o(1) class Solution { public: ListNode* ReverseList(ListNode* head) { if(head == nullptr) return nullptr; while(head != nullptr) { pNext = head->next; head->next = pTemp; pTemp = head;...