struct ListNode* removeElements(struct ListNode* head, int val){
struct ListNode* prev = NULL;
struct ListNode* cur = head;
while(cur)
{
if(cur->val != val)
{
prev = cur;
cur = cur->next;
}
else
{
struct ListNode* next = cur->next;
if(prev == NULL)//第一个结点就是val，删除，下一个结点作为新头
{
free(cur);
head = next;//新头
cur = next;
}
else
{
free(cur);
prev->next = next;
cur = next;
}
}
}
return head;
}
二、
方法一：头插法
struct ListNode* reverseList(struct ListNode* head){
struct ListNode* newhead = NULL;
struct ListNode* cur = head;
//头插
while(cur)
{
struct ListNode* next = cur->next;
cur->next = newhead;
newhead = cur;
cur = next;
}
return newhead;
}
方法二：设置三个指针翻转方向
struct ListNode* reverseList(struct ListNode* head){
if(head == NULL)
return NULL;
struct ListNode* n1,*n2,*n3;
n1 = NULL;
n2 = head;
n3 = n2->next;
while(n2)
{
n2->next = n1;
n1 = n2;
n2 = n3;
if(n3)
{
n3 = n3->next;
}
}
return n1;
}
三、
struct ListNode* middleNode(struct ListNode* head){
struct ListNode* slow = head;//慢函数
struct ListNode* fast = head;//快函数
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
四、
思路：
fast先走k步，slow和fast再同时走，fast走到尾时，slow就是倒数第k个
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
struct ListNode* slow,*fast;
slow = fast = pListHead;
while(k--)
{
//如果k大于链表长度
if(fast == NULL)
return NULL;
fast = fast->next;
}
while(fast)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}
五、
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
if(list1 == NULL)
return list2;
if(list2 == NULL)
return list1;
struct ListNode* head = NULL,*tail = NULL;
while(list1&&list2)
{
if(list1->val > list2->val)
{
if(tail == NULL)
{
head = tail = list2;
}
else
{
tail->next = list2;
tail = list2;
}
list2 = list2->next;
}
else
{
if(tail == NULL)
{
head = tail = list1;
}
else
{
tail->next = list1;
tail = list1;
}
list1 = list1->next;
}
}
while(list1)//将剩下的结点全部放到后面
{
tail->next = list1;
tail = list1;
list1 = list1->next;
}
while(list2)
{
tail->next = list2;
tail = list2;
list2 = list2->next;
}
return head;
}
六、
C++兼容C语言，可用C语言做C++题
思路：
遍历整个链表，把 < x的插入到一个链表1中，把 >= x的插入链表2中，最后把两个表链接起来
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
struct ListNode* lessHead ,*lessTail ,*greatHead ,*greatTail;
lessTail = lessHead =(struct ListNode*)malloc(sizeof(struct ListNode));
greatHead = greatTail =(struct ListNode*)malloc(sizeof(struct ListNode));
lessTail->next = greatTail->next = NULL;
struct ListNode* cur = pHead;
while(cur)
{
if(cur->val < x)
{
lessTail->next = cur;
lessTail = lessTail->next;
}
else
{
greatTail->next = cur;
greatTail = greatTail->next;
}
cur = cur->next;
}
lessTail->next = greatHead->next;
greatTail->next = NULL;//记得要把链尾制NULL
struct ListNode* list = lessHead->next;
free(lessHead);
free(greatHead);
return list;
}
};
七、
思路：
class PalindromeList {
public:
struct ListNode* middleNode(struct ListNode* head)//利用快慢指针求中间点
{
struct ListNode* slow = head;//慢函数
struct ListNode* fast = head;//快函数
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
struct ListNode* reverseList(struct ListNode* head)//翻转链表
{
struct ListNode* newhead = NULL;
struct ListNode* cur = head;
//头插
while(cur)
{
struct ListNode* next = cur->next;
cur->next = newhead;
newhead = cur;
cur = next;
}
return newhead;
}
bool chkPalindrome(ListNode* A) {
struct ListNode* mid = middleNode(A);//找到链表中点位置
struct ListNode* newhead = reverseList(mid);//翻转链表中点以后的结点
//从头开始和从中间开始，判断结点是否相等
while(A&&newhead)
{
if(A->val == newhead->val)
{
A = A->next;
newhead = newhead->next;
}
else
return false;
}
return true;
}
};
八、
思路：
1.A链表找到尾结点，B链表找到尾结点，尾结点的地址相同就是相交
2.求出两个链表的长度，lenA和lenB，长的先走（lenA-lenB），再一起走，第一个地址相等就是交点
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode* tailA = headA ,*tailB = headB;
int lenA = 1, lenB = 1;
while(tailA->next)
{
tailA = tailA->next;
++lenA;
}
while(tailB->next)
{
tailB = tailB->next;
++lenB;
}
//这样设定，无论哪个长短，最后shortlist和longlist都是正确的
struct ListNode* shortlist = headA ,*longlist = headB;
if(lenA > lenB)
{
longlist = headA;
shortlist = headB;
}
int gap = abs(lenA-lenB);
while (gap--) {
longlist = longlist->next;
}
while(shortlist && longlist)
{
if(shortlist == longlist)
{
return shortlist;
}
else
{
shortlist = shortlist->next;
longlist = longlist->next;
}
}
return NULL;
}
九、
思路：快慢指针
bool hasCycle(struct ListNode *head) {
struct ListNode*slow ,*fast;
slow = fast = head;
while(fast&&fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)//若slow和fast相遇，则证明有环
return true;
}
return false;
}
十、
思路：
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode* slow,*fast;
slow = fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
{
struct ListNode* meet = slow;
while(meet != head)
{
meet = meet->next;
head = head->next;
}
return meet;
}
}
return NULL;
}
十一、
思路：
1.拷贝节点连接在原节点后面
2.更新拷贝节点的random
3.拷贝节点解下来，连接到一起
struct Node* copyRandomList(struct Node* head)
{
struct Node* cur = head;
//1.拷贝节点连接在原节点后面
while(cur)
{
struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
copy->val = cur->val;
copy->next = cur->next;
cur->next = copy;
cur = cur->next->next;
}
//2.更新拷贝节点的random
cur = head;
while(cur)
{
struct Node* copy = cur->next;
if(cur->random == NULL)
{
copy->random = NULL;
}
else
{
copy->random = cur->random->next;
}
cur = copy->next;
}
//3.拷贝节点解下来，连接到一起
struct Node* copyHead = NULL, *copyTail = NULL;
cur = head;
while(cur)
{
struct Node* copy = cur->next;
struct Node* next = copy->next;
// copy解下来尾插
if(copyTail == NULL)
{
copyHead = copyTail = copy;
}
else
{
copyTail->next = copy;
copyTail = copy;
}
cur->next = next;
cur = next;
}
return copyHead;
}
