技巧
- 假头
- 新链表
- 双指针（正反向指针，快慢指针）
- 递归
例子：
1.合并两个有序链表（假头，新链表）
-
链表反转（假头/递归）
image.png
//Definition for singly-linked list.
struct ListNode {
int val;
struct ListNode *next;
};
//递归实现
struct ListNode* reverseList(struct ListNode* head){
if (head == NULL || head->next == NULL)
return head;
struct ListNode*cur,*next;
cur= head;
next=cur->next;
struct ListNode* newH = reverseList(next);
next->next= cur;
cur->next = NULL;
return newH;
}
-
K个一组反转（假头/递归/多指针）
image.png
struct ListNode*reverse(struct ListNode* head) {
struct ListNode* result = NULL;
struct ListNode* p = head, *next=NULL;
while(p) {
next= p->next;
p->next=result;
result=p;
p=next;
}
return result;
}
struct ListNode* reverseKGroup(struct ListNode* head, int k){
struct ListNode* dummy = malloc(sizeof(struct ListNode));
struct ListNode* former;
struct ListNode* start, *end,*p, *follow;
int len;
dummy->next = head;
p=dummy;
while(p) {
len = k;
//1.get former;
former = p;
//2.get start
start = former->next;
//3.check have k numbers
while( p->next && len) {
p=p->next;
len--;
}
//4.不足k个，不处理
if (len > 0)
break;
//5.get end;
end = p;
//6.get follow
follow = p->next;
//7. 处理[former, follow]
end->next = NULL;
former->next=NULL;
reverse(start);
former->next = end;
start->next = follow;
p = start;
}
return dummy->next;
}
