目录

输出单链表的倒数第K个节点删除单链表中间节点反转单链表递归实现

输出单链表的倒数第K个节点

  题目描述：在单链表中输出倒数第k个节点   要求：如果链表长为N，时间复杂度为O(N)，额外空间复杂度达到O(1)   思路：当我们用num来表示链表中节点个数，当我们输出节点的时候会出现三种情况：

不存在第k个节点，此时返回空（num<k）；第k个节点就是第一个节点，操作较容易（num==k）；第k个节点在链表中（num>k），此时输出倒数第k个节点相当于输出第（num-k+1）个节点；

  除了我们可遍历两次链表第一次记录下倒数k的位置这种方法，我们还可通过定义两个指针实现只遍历一次就可找到倒数第k位置：第一个指针从链表头节点开始遍历k-1步，此时第二人个指针不动；从第k步开始第二个指针也从链表头指针开始向后遍历，此时两个指针的距离为k-1，当第一个指针到达链表尾时，第二个指针指向的就是倒数第k个节点。

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution{ pubilc: ListNode* FindkthToTail(ListNode* pListHead, unsigned int k){ if(pListHead == nullptr || k == 0) //解决潜在危险 return nullptr; ListNode *pAhead = pListHead； ListNode *pBbehind = nullptr; for(unsigned int i=0; i<k-1; ++i) { if(pAhead->next != nullptr)// 判断链表节点数小于k pAhead = pAhead->next; else return nullptr; } pBehind = pListHead; while(pAhead->next != nullptr) { pAhead = pAhead->next; pBbehind = pBbehind->next; } return pBbehind; } }

删除单链表中间节点

  题目描述：给定链表头节点head，实现删除链表的中间节点。例：

1->2,删除节点1；1->2->3,删除节点2；1->2->3->4;删除节点2；1->2->3->4->5,删除节点3.

  要求：如果链表长为N，时间复杂度为O(N)，额外空间复杂度达到O(1)   思路：首先我们还是要考虑特殊情况，当给定的头指针为空指针，或者只有只有一个节点的时候，直接返回头节点即可；借鉴上面的方法，我们可知道可以通过快慢指针进行一次链表遍历后找到要删除的节点：快指针一次遍历两个节点，慢指针一次遍历一个节点，当快指针遍历完后，慢指针所指向的节点就为要删除的节点：

class Solution{ pubilc: Node removeMidNode(Node head){ if(head == null || head.next == null) return head; if(head.next.next == null) return head.next; Node fast = head.next.next; //走两步的指针 Node slow = head; //走一步的指针 //快指针遍历链表后，慢指针指向删除节点 while(fast.next != null && fast.next.next != null){ fast = fast.next.next; slow = slow.next; } slow.next = slow.next.next return head; } }

反转单链表

  题目描述：反转给定的单链表。例：

1->2->3->4 反转后为

4->3->2->1

  要求：如果链表长为N，时间复杂度为O(N)，额外空间复杂度达到O(1)   思路：当我们调整当前节点，使他的next指向它的前驱，不过在做该操作时需要注意保存该节点的原next防止链表断裂，以你我们可设置三个指针，分别指向当前节点、前一个节点和后一个节点：

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* ReverseList(ListNode* pHead) { ListNode* pReversedHead = nullptr; ListNode* pNode = pHead; ListNode* pPrev = nullptr; while(pNode!=nullptr) { ListNode* pNext = pNode->next; if(pNext == nullptr) pReversedHead = pNode; pNode->next = pPrev; pPrev = pNode; pNode = pNext; } return pReversedHead; } };

递归实现

  这种递归虽然简洁但是很不好理解，递归的两个条件：

终止条件是大观前街店或下一个节点==null在函数内部，改变结点的指向，就是下面的 head->next->next = head;

  该方法可结合幻灯片理解：推荐：动画演示+多种解法 面试题24. 反转链表

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { if(head == NULL || head->next == NULL) return head; ListNode *cur = reverseList(head->next); head->next->next = head; head->next = NULL; return cur; } };