1.求链表倒数第K个节点
ahead指针先走K-1步,behind指针开始走,ahead走到末尾,此时behind刚好是倒数第K个
2.求链表中间节点
ahead指针一次走2步,behind一次走1步,当ahead走到末尾时,behind刚好是中间节点
3.判断链表是否成环
ahead指针一次走2步,behind一次走1步,当ahead走到末尾时,还没有追上behind说明无环。如果没有到末尾就遇上了,说明有环。
4.链表反转
2个指针相邻同步后移,不停后者next改指向前者
ListNode* reverseList(ListNode* head)
{ListNode* result = NULL;//反转后的头节点ListNode* cur = head;ListNode* pre = NULL;while(cur != NULL){ListNode* next = cur->next;//覆盖前先记录旧值if(next == NULL){result = cur;//记录尾节点}cur->next = pre;//改变cur节点next指针指向前者pre = cur;cur = next;//同步后移}return result;
}
5.链表合并
ListNode* mergeList(ListNode* head1, ListNode* head2)
{if(head1 == NULL)return head2;else if(head2 == NULL)return head1;if(head1->data > head2->data){//保证head1头节点小于等于head2头节点,合并后头节点就是head1int temp = head2->data;head2->data = head1->data;head1->data = temp;}ListNode* cur1 = head1;while(head2 != NULL)//依次将链表2节点插入链表1合适位置{while(cur1->next != NULL && cur1->next->data < head2->data)cur1 = cur1->next;//此时cur1 <= head2 <= cur1->next或者cur1是尾节点但不大于head2,将head2插在cur后即可ListNode* tmp = head2;head2 = head2->next;tmp->next = cur1->next;cur1->next = tmp;}return head1;
}