移除链表元素
这道题有多种思路，双指针法
思路：遍历一遍，在中途中我们要找出要删除的节点，并把要删除的节点进行free，我们要注意的就是
我们通过判断tail->val是否为要删除的值,如果不是就prev = tail, tail = tail->next,如果是的话,我们就要删除, 然后tail存储下一个节点的地址,而prev不变,
我们要考虑一些情况,当我们删除的是第一个节点,那head存储的地址就要改变,
循环结束的条件就是
tail的值为NULL,就是循环停止的时候
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* cur = head; struct ListNode* prev = NULL; //遍历一遍 while (cur) { if (cur->val == val) { struct ListNode* nex = cur->next; if (prev) { prev->next = nex; } //判断是否要删除第一个节点 else { head = nex; } free(cur); cur = nex; } else { prev = cur; cur = cur->next; } } return head; }
二指针加空链表法(尾插思路)
cur去判断该节点是否符合,引用新的newhead指向符合条件的节点,符合就添加到newhead,不是就free,然后cur指向下一个节点,tail不动,有两种特殊情况,一种的head=NULL,一种是free最后一个节点,前一个节点的next没有NULL
struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* newnode = NULL; struct ListNode* cur = head; struct ListNode* tail = NULL; while (cur) { if (cur->val != val) { if (tail == NULL) { newnode = cur; tail = cur; } else { tail->next = cur; tail = cur; } cur = cur->next; } else { //保存下一个节点 struct ListNode* p = cur->next; free(cur); cur = p; } } //假设head为NULL if (tail) tail->next = NULL; return newnode; }
哨兵位方法
这里的头节点不是d1而是head也称哨兵位头节点
这个带哨兵位的链表的好处就是头节点一定存在,地址不为空,
struct ListNode* removeElements(struct ListNode* head, int val) { //创建哨兵位 struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* cur = head; struct ListNode* tail = newnode; while (cur) { if (cur->val != val) { tail->next = cur; cur = cur->next; tail = tail->next; } else { //保存下一个节点 struct ListNode* p = cur->next; free(cur); cur = p; } } //假设head为NULL tail->next = NULL; //释放哨兵 struct ListNode*p = newnode->next; free(newnode); return p; }
分割链表
方法1:创建两个空链表 链表1存储小于X的所有节点，链表2存储大于等于x的所有节点，然后两个链表链接起来，
ListNode* partition(ListNode* pHead, int x) { //小 struct ListNode *head1 = (struct ListNode *)malloc(sizeof(struct ListNode)); struct ListNode *tail1 = head1; //大 struct ListNode *head2 = (struct ListNode *)malloc(sizeof(struct ListNode)); struct ListNode *tail2 = head2; struct ListNode *cur = pHead; while (cur) { if(cur->val < x) { tail1->next = cur; tail1 = tail1->next; } else { tail2->next = cur; tail2 = tail2->next; } cur = cur->next; } //防止head2最后一个节点的next不为NULL tail2->next = NULL; tail1->next = head2->next; struct ListNode *ph = head1->next; free(head1); free(head2); return ph; }
我们需要注意的是head2的最后一个节点的next可能指向野指针,也可能形成环状链表,
反向链表
方法1
三指针反转
主要进行交换的是n1和n2这两个指针,n3指针是辅助n2能找到下一个节点的地址
循环结束就是
当n2 = NULL或者是n1->next = NULL循环结束
struct ListNode* reverseList(struct ListNode* head) { if (head == NULL) return head; struct ListNode *n1 = NULL; struct ListNode *n2 = head; struct ListNode *n3 = head->next; while(n2) { n2->next = n1; n1 = n2; n2 = n3; if(n3) n3 = n3->next; } return n1; }
方法二:创建空链表,头插
思路:把旧链表的节点取下来,然后头插到新链表中
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* newnode = NULL; struct ListNode* cur = head; while(cur) { struct ListNode* pn = cur->next; cur->next = newnode; newnode = cur; cur = pn; } return newnode; }
链表中倒数第k个结点
方法1暴力法
先求出链表的长度,然后长度减去倒数的个数,再遍历一遍
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { struct ListNode* tail = pListHead; if (tail) { int size = 1; while (tail->next) { tail = tail->next; size++; } tail = pListHead; if (k > size) { return NULL; } while (size > k) { tail = tail->next; size--; } return tail; } else { return NULL; } }
时间复杂度是O(n)
但是不够高效
方法二
双指针距离差
创建两个指针,指向头节点,然后一个一个节点也走k步,然后两个指针一起走,当走k步的那个指针为NULL就结束 
结束标记
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { struct ListNode* fast = pListHead, *slow = pListHead; //fast先走k步 while(k--) { //防止为空 if(fast ==NULL) return NULL; fast = fast->next; } //一起走 while (fast) { fast = fast->next; slow = slow->next; } return slow; }
链表练习题-2
