1.单链表逆序，要求在原链表数据不改变的情况下进行逆序
方法一：
新建一个头节点，将链表中的元素一个一个放入新的头节点
struct ListNode* reverseList(struct ListNode* head){
struct ListNode* n = malloc(sizeof(struct ListNode));
n->next = NULL;
struct ListNode* p = NULL;
for(;head!= NULL;)
{
p = head;
head=head->next;
p->next = n->next;
n->next = p;
}
return n->next;
}
方法二：
直接在原链表操作，遍历节点，将每个节点放在链表最前面(在原来的链表有头节点的情况下)
struct ListNode* ReverseList(struct ListNode* head){
if(!head||!head->next)return head;
struct ListNode* node = head;
for(struct ListNode* n = head->next;n->next!=NULL;)
{
struct ListNode* temp = n->next;
n->next = temp->next;
temp->next = head->next;
node->next = temp;
}
return head;
}
1: head(node) n next(temp) next next next
0 1 2 3 4 5
head(node) next(temp) n next next next
0 2 1 3 4 5
2: head(node) next n next(temp) next next
0 2 1 3 4 5
head(node) next(temp) next n next next
0 3 2 1 4 5
2.找出单链表中倒数第n个节点
方法一：反转链表，找到第n个节点（题目要求，如果对于该节点的next无要求）
struct ListNode* FindKthToTail(struct ListNode* pHead, int k ){
ReverseList(struct ListNode* pHead);
while(--k)//如果有头节点，换成k--
{
pHead = pHead->next;
}
return pHead;
}
方法二：遍历一遍，求出链表共多长，再计算出要next的次数，找到该节点(无头节点版本)
struct ListNode* FindKthToTail(struct ListNode* pHead, int k ){
if(!head)return pHead;
int i = 1;
struct ListNode* node = pHead;
while(node = node->next)++i;
i -= k;
if(i > 0)return NULL;
while(i--)
{
pHead = pHead->next;
}
return pHead;
}
方法三：按照k的值，在next k次后，再从头开始用新指针遍历，直到旧指针遍历到NULL结束(无头节点)
struct ListNode* FindKthToTail(struct ListNode* pHead, int k ){
if(!head)return pHead;
struct ListNode* old = pHead;
struct ListNode* n = pHead;
while(--k)
{
old = old->next;
if(NULL == old)return NULL;
}
while(NULL != old)
{
old = old->next;
n = n->next;
}
return n;
}
3.判断单链表中是否有环
方法一：覆盖链表中的值（会破坏链表），如果又一次遇到覆盖过的节点，则有环
bool hasCycle(struct ListNode *head) {
if(head == NULL)return false;
while(head->next)
{
head->val = 'bjfuvth';
head = head->next;
if(head->next->val == 'bjfuvth')return true;
}
return false;
}
方法二：利用快慢指针 p1 = p1->next;p2 = p2->next;如果遍历到NULL，则没有环，如果遍历到两个指针相遇，则有环(例如地球是圆的)
bool hasCycle(struct ListNode *head) {
if(head == NULL)return false;
struct ListNode* q = head;
struct ListNode* p = q;
while(q!= NULL && q->next!= NULL)
{
q = q->next->next;
p = p->next;
if(q == p)return true;
}
return false;
}
4、找出环形单链表的环的入口位置
方法一：
- 1.第一次相遇，slow = nb
- 2.a+nb = 入口点
- 3.slow再走a = 入口 = head走到入口 = a
- 4.由3得出，起始距离入口 = 第一次相遇位置 + a
struct ListNode *detectCycle(struct ListNode *head) {
if(!head)return NULL;
struct ListNode* fast = head;
struct ListNode* slow = head;
while(fast!= NULL && fast->next!= NULL)
{
fast = fast->next->next;
slow = slow->next;
if(fast == slow)break;
}
if(fast == NULL)return;
fast = head;
while(fast != slow)
{
fast = fast->next;
slow = slow->next;
}
return fast;
}
5.合并两个有序的单链表生成一个有序的单链表
方法一：直接对两个链表进行比较，插入
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
if(list1 == NULL)return list2;
if(list2 == NULL)return list1;
if(list1->val > list2->val)return mergeTwoLists(list2,list1);
struct ListNode* n1 = list1->next;
struct ListNode* n2 = list2;
struct ListNode* n = list1;
while(1)
{
if(NULL == n1)
{
n->next = n2;
break;
}
if(NULL == n2)
{
n->next = n1;
break;
}
if(n1->val > n2->val)
{
n->next = n2;
n = n2;
n2 = n2->next;
}
else
{
n->next = n1;
n = n1;
n1 = n1->next;
}
}
return list1;
}
方法二：递归
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
if(list1 == NULL)return list2;
if(list2 == NULL)return list1;
if(list1->val < list2->val)
{
list1->next = mergeTwoLists(list1->next,list2);
return list1;
}
else
{
list2->next = mergeTwoLists(list1,list2->next);
return list2;
}
}
6.判断两个单链表是否是Y型链表
方法一：指针q在链表遍历完继续遍历B链表，指针p在链表B遍历完继续遍历链表A
相当于q指针遍历了链表A+链表B，p指针遍历了链表B+链表A。遍历的长度是一样的。
如果没有相交点，最后都会回到NULL，p == q，返回NULL
如果有相交点，把AB链表分解为，相交点前的链表A和链表B，和相交点后的链表C
指针q遍历顺序 = A->C->B
指针p遍历顺序 = B->C->A
最后都会在相交点相遇（走到尽头见不到你，于是走过你来时的路，等到相遇时才发现，你也走过我来时的路。）
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
if(!headA || !headB)return NULL;
struct ListNode* q = headA;
struct ListNode* p = headB;
while(q != p)
{
q = q ? q->next:headB;
p = p ? p->next:headA;
}
return p;
}