链表操作的几个高效技巧

1. 快慢指针

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

```ListNode* removeNthFromEnd(ListNode* head, int n) {
for(int i = 0; i < n; i++)
back = back->next;
if(back == NULL) {
delete tmp;
}
while(back->next != NULL) {
front = front->next;
back = back->next;
}
ListNode * tmp = front->next;
front->next = tmp->next;
delete tmp;
}```

```bool hasCycle(ListNode *head) {
while(fast != NULL && fast->next != NULL && slow != fast) {
fast = fast->next->next;
slow = slow->next;
}
return (fast != NULL && fast->next != NULL);
}```

2. 虚结点

```ListNode* removeElements(ListNode* head, int val) {
ListNode * dummy = new ListNode(-1);
ListNode * prev = dummy;
while(p != NULL) {
if(p->val == val) {
prev->next = p->next;
delete p;
}
else {
prev = p;
}
p = prev->next;
}
delete dummy;
}```

```ListNode* partition(ListNode* head, int x) {
ListNode * dummy = new ListNode(-1);
ListNode * prev = dummy;
while(first != NULL && first->val < x) {
first = first->next;
prev = prev->next;
}
if(first == NULL || first->next == NULL) {
delete dummy;
}
ListNode * p = first->next;
ListNode * q = first;
while(p != NULL) {
if(p->val < x) {
q->next = p->next;
p->next = prev->next;
prev->next = p;
p = q->next;
prev = prev->next;
} else {
p = p->next;
q = q->next;
}
}
delete dummy;
}```

4. 问题转换

```A:          a1 → a2
↘
c1 → c2 → c3
↗
B:     b1 → b2 → b3```

1. 解单链表有环问题I，得到环中一指针。

2. 以得到的指针断开这个环。

3. 解两单链表交叉结点问题，得到最终结果。

```ListNode *detectCycle(ListNode *head) {
while(fast != NULL && fast->next != NULL && slow != fast) {
slow = slow->next;
fast = fast->next->next;
}
if(fast == NULL || fast->next == NULL) {
return NULL;
}
ListNode * tail1 = slow;
tail1->next = NULL;
int length1 = 0;
while(p != NULL) {
length1++;
p = p->next;
}
int length2 = 0;
while(p != NULL) {
length2++;
p = p->next;
}
if(length1 > length2) {
int k = length1 - length2;
} else if ( length2 < length1) {
int k = length2 - length1;
}
}