首页 > 代码库 > 我要好offer之 链表大总结
我要好offer之 链表大总结
单链表是一种递归结构，可以将单链表看作特殊的二叉树(我把它叫做一叉树)
单链表的定义：
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
1. O(1)时间删除结点
ListNode* DeleteNode(ListNode* pHead, ListNode* deletedNode) { assert(pHead != NULL && deletedNode != NULL); ListNode newHead(-1); newHead.next = pHead; if (pHead == deletedNode) { newHead->next = pHead->next; delete deletedNode; deketedNode = NULL; return newHead.next; } else { if (deleteNode->next == NULL) { ListNode* cur = pHead; while (cur->next != deleteNode) { cur = cur->next; } cur->next = NULL; delete deletedNode; deletedNode = NULL; return newHead.next; } else { ListNode* nextNode = deletedNode->next; deletedNode->val = nextNode->val; deletedNode->next = nextNode->next; delete nextNode; nextNode = NULL; return newHead.next; } }}
2. 单链表反转
ListNode* ReverseList(ListNode* pHead) { if (pHead == NULL || pHead->next == NULL) { return pHead; } ListNode* tail = pHead; ListNode* cur = pHead->next; while (cur != NULL) { ListNode* nextNode = cur->next; cur->next = pHead; pHead = cur; cur = nextNode; } tail->next = NULL; return pHead;}
3. 单链表倒数第k个结点
ListNode* KthNode(ListNode* pHead, int k) { assert(pHead != NULL && k > 0); ListNode* first = pHead; ListNode* second = pHead; while (first != NULL && k > 0) { first = first->next; --k; } if (first == NULL) { if (k == 0) { return pHead; } else { return NULL; } } while (first != NULL) { first = first->next; second = second->next; } return second;}
4. 单链表反转部分区间
5. 单链表快速排序的一趟划分
6. 单链表去掉重复元素
7. 单链表旋转
8. 单链表成对交换节点
9. 有序单链表归并排序
10. 单链表加法运算
11. 单链表是否存在环，环的位置
12. 两个单链表的第一个公共结点
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。