一、移除链表元素

题目：

思路1：

在原来的链表上进行修改，节点的数据是val的删除，然后前后再连接起来。

需要考虑的因素：
1.要删除的节点位置在第一个节点；
2.要删除的节点位置在中间任意一个节点；
3.要删除的节点位置在最后一个节点

用一个变量cur遍历链表，要删除的节点是头节点，就是头删；是中间的某个节点就把要删除的节点free释放，然后连接前后的节点（定义另一个变量prev为cur的前一个）；是最后一个节点，就是尾删，但是这里的尾删与中间某个节点删除是一样的。

struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur=head;struct ListNode* prev=NULL;while(cur){if(cur->val==val){if(cur==head){head=cur->next;free(cur);cur=head;}else{prev->next=cur->next;//cur是尾节点next就是空free(cur);cur=prev->next;}}else{prev=cur;cur=prev->next;}}return head;
}

思路2：

将不是要移除的元素连接到新的链表

这里我们要定义一个新的头指针（newhead），还要一个变量cur去遍历原链表，找不是要移除的元素；再定义一个变量tail使每次插入的新节点链接起来。

注意：在最后要把tail的next置空，因为尾节点的next必须指向空指针

struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur = head;struct ListNode* newhead=NULL;struct ListNode* tail = newhead;while(cur){if(cur->val==val){cur=cur->next;}else{if(tail==NULL){newhead=tail=cur;}else{tail->next=cur;tail=tail->next;}cur=cur->next;}}if(tail){tail->next=NULL;}return newhead;
}

二、反转链表

题目：

采用头插法

定义一个新的头指针newhead指向NULL，用一个变量cur遍历原链表，再定义一个变量del为cur的下一个节点（这样cur循环一次可以到原来链表的下一个节点）。头插时，让cur的next指向newhead，再把newhead移到cur的位置上去，直到把原链表的所有节点头插完，返回的newhead就是原链表的反转。

struct ListNode* reverseList(struct ListNode* head)
{//头插struct ListNode* newhead=NULL;struct ListNode* cur=head;while(cur){struct ListNode* del=cur->next;cur->next=newhead;newhead=cur;cur=del;}return newhead;
}

三、链表的中间节点

题目：

快慢指针法

定义两个指针变量fast(快指针)和slow(慢指针)，快指针一次走两步，慢指针一次走一步。当快指针或者快指针的next有一个为空指针时，跳出循环，返回慢指针，就是中间节点。

struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow = head;struct ListNode* fast = head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;}return slow;
}

四、链表中倒数第k个节点

题目：

快慢指针相对距离法

定义两个指针变量fast和slow，先让fast走k步（如果fast已经为空k还没结束就返回空），然后fast和slow一起走（速度相同），当fast为空时跳出循环，此时的slow就是倒数第k个节点。

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
{struct ListNode* slow = pListHead;struct ListNode* fast = pListHead;while(k)//先走k步{if(fast==NULL){return NULL;}fast=fast->next;k--;}while(fast!=NULL)//相对距离{fast=fast->next;slow=slow->next;}return slow;
}

五、回文结构

题目：

这道题其实是前面两个题的综合
采用找中间节点和反转链表，然后比较是否回文

先找到中间节点，然后在这个中间节点开始反转后面的节点，比较从头节点开始到中间节点的个数，如果相同，就是回文，返回true；否则返回false。

class PalindromeList {
public:ListNode* find(ListNode* head){ListNode* slow=head;ListNode* fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}return slow;}ListNode* reverse(ListNode* head){ListNode* newhead=NULL;ListNode* cur=head;while(cur){ListNode* del=cur->next;cur->next=newhead;newhead=cur;cur=del;}return newhead;}bool chkPalindrome(ListNode* head) {ListNode* rid=find(head);ListNode* mrid=reverse(rid);ListNode* cur=head;while(cur!=rid){if(cur->val!=mrid->val){return false;}cur=cur->next;mrid=mrid->next;}return true;}
};

六、合并两个有序链表

题目：

两个链表的节点从头开始比较，取小的尾插到新链表；如果有一个链表的节点还没尾插完，就直接将这个链表的剩余节点尾插到新链表去。

如果刚开始有某个链表为空，就直接返回另一个链表

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if(list1==NULL){return list2;}if(list2==NULL){return list1;}struct ListNode* head=NULL;struct ListNode* tail=NULL;while(list1&&list2){if(list1->val<=list2->val){if(tail==NULL){head=tail=list1;}else{tail->next=list1;tail=tail->next;}list1=list1->next;}else{if(tail==NULL){head=tail=list2;}else{tail->next=list2;tail=tail->next;}list2=list2->next;}}if(list1){tail->next=list1;}if(list2){tail->next=list2;}return head;
}

感谢观看~