刷算法题之链表专题

链表的定义：用一组任意的存储单元存储线性表的数据元素。
注意：存储单元可以是连续的，也可以是不连续的
链表的分类:
静态链表：
动态链表：

leetcode203

删除链表中的元素的时候，

// 对原链表操作
struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode *tmp; // 存放临时节点，while( head != NULL && head->val == val) // 若链表中的元素 [1,1,1,1,1] 删除的头节点{tmp = head;head = head->next;free(tmp); // 要释放的元素}struct ListNode * curt = head; // 删除的元素并不会改变头节点while(curt != NULL && (tmp = curt->next)){  if(tmp->val == val) // 若cur->next的值等于val{  curt->next = tmp->next; // 改变链表的前驱, 将cur->next设置为cur->next->next并删除cur->nextfree(tmp);} else {curt = curt->next;} }return head;
}// 构造一个虚拟头节点
struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* new_head= (struct ListNode*)malloc(sizeof(struct ListNode));new_head->next = head; // 为head构造一个虚拟节点的前驱节点struct ListNode *cur = new_head; // 将当前节点指向headwhile(cur->next != NULL){if(cur->next->val == val){struct ListNode *tmp = cur->next;cur->next = cur->next->next;free(tmp);}else{cur = cur->next;}}head = new_head->next;free(new_head);return head;
}

leetcode707
考察链表的基本的操作，增删改查。

typedef struct Node{int data;struct LNode *lnext;
}LNode;typedef struct {int val;LNode *next;
} MyLinkedList;MyLinkedList* myLinkedListCreate() {MyLinkedList *obj = (MyLinkedList *)malloc(sizeof(MyLinkedList));LNode *head = (LNode *)malloc(sizeof(LNode));if (!obj || !head){return -1; // 分配空间失败 直接退出}head->lnext = NULL;obj->next = head;obj->val = 0;return obj;
}int myLinkedListGet(MyLinkedList* obj, int index) {if (index < 0 || index >= obj->val) {return -1;}LNode *cur = obj->next;while(index-- >= 0){cur = cur->lnext;}return cur->data;
}void myLinkedListAddAtHead(MyLinkedList* obj, int val) {LNode *node = (LNode *)malloc(sizeof(LNode));node->data = val;node->lnext = obj->next->lnext;obj->next->lnext = node;obj->val ++;}void myLinkedListAddAtTail(MyLinkedList* obj, int val) {LNode * cur = obj->next;while(cur->lnext != NULL){cur = cur->lnext;}LNode * temp = (LNode *)malloc(sizeof(LNode));temp->data = val;temp->lnext = NULL;;cur->lnext = temp;obj->val++;
}void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {if(index > obj->val) {return;}LNode * cur = obj->next;while(index-- > 0){cur = cur->lnext;}LNode * temp = (LNode *)malloc(sizeof(LNode)); // 为插入的节点开辟空间temp->data = val;temp->lnext = cur->lnext;cur->lnext = temp;obj->val++;
}void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {if(index < 0 || index >= obj->val){return;}LNode *cur = obj->next;while(index-- > 0) {cur = cur->lnext;}LNode * temp = cur->lnext;cur->lnext = temp->lnext;free(temp);obj->val--;
}void myLinkedListFree(MyLinkedList* obj) {LNode *tmp = obj->next;while(tmp != NULL){LNode *n = tmp;tmp = tmp->lnext;free(n); }free(obj);
}/*** Your MyLinkedList struct will be instantiated and called as such:* MyLinkedList* obj = myLinkedListCreate();* int param_1 = myLinkedListGet(obj, index);* myLinkedListAddAtHead(obj, val);* myLinkedListAddAtTail(obj, val);* myLinkedListAddAtIndex(obj, index, val);* myLinkedListDeleteAtIndex(obj, index);* myLinkedListFree(obj);
*/

leetcode206
链表反转：头变尾，尾变头
思路：使用双指针处理这道题

struct ListNode* reverseList(struct ListNode* head) {struct ListNode *cur = head; //保存cur的下一个结点struct ListNode *temp; // 中间变量struct ListNode *pre = NULL; // /pre指针指向前一个当前结点的前一个结点while( cur != NULL){temp = cur->next;    //保存下一个结点的位置cur->next = pre; //翻转操作pre = cur; //更新结点cur = temp;}return pre; // 
}// 递归解法
struct ListNode *reverse(struct ListNode *pre, struct ListNode *cur)
{// 遍历的终止条件if(cur == NULL){return pre;}struct ListNode *temp = curt->next;curt->next = pre;return reverse(cur, temp);
}
struct ListNode *reverseList(struct ListNode *head)
{return reverse(NULL, head);
}