本文共 7064 字，大约阅读时间需要 23 分钟。

1. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
       if(l1 == NULL)         return l2;    if(l2 == NULL)        return l1;    struct ListNode* tail = NULL;    struct ListNode* head = NULL;    struct ListNode* cur1 = l1;    struct ListNode* cur2 = l2;    while(cur1 && cur2) {
           if(cur1->val < cur2->val) {
               if(head == NULL) {
                   head = cur1;                tail = cur1;                cur1 = cur1->next;            }            else {
                   tail->next = cur1;                tail = tail->next;                cur1 = cur1->next;                            }        }        else {
               if(head == NULL) {
                   head = cur2;                tail = cur2;                cur2 = cur2->next;            }            else{
                   tail->next = cur2;                cur2 = cur2->next;                tail = tail->next;            }        }    }    if(cur2 == NULL) {
           tail->next = cur1;    }    else{
           tail->next = cur2;    }    return head;}

2. 给定一个链表，判断链表中是否有环。

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     struct ListNode *next; * }; */typedef struct ListNode Node;bool hasCycle(struct ListNode *head) {
       Node* fast = head;    Node* slow = head;    if(head == NULL){
           return false;    }    if(head->next == NULL  ) {
           return false;    }    while(fast != NULL && fast->next != NULL) {
     //快慢指针注意判断 fast 当前和下一个都不为空        fast = fast->next->next;        slow = slow->next;        if(fast == slow) {
               return true;        }    }    return false;}

3. 判断两个链表是否相交

typedef struct ListNode Node; struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
       Node* curA = headA;    Node* curB = headB;    Node *longerlist = headA;	Node *shortlist = headB;    int gap;    int lengthA = 0;    int lengthB = 0;    while(curA){
           ++lengthA;        curA = curA->next;    }    while(curB){
           ++lengthB;        curB = curB->next;    }    gap = abs(lengthA - lengthB);//求多余部分长度	if (lengthA < lengthB)	{
   		longerlist = headB;		shortlist = headA;	}	while(gap--) {
           longerlist = longerlist->next;    }    while(longerlist) {
           if(longerlist == shortlist)            return longerlist;        longerlist = longerlist->next;        shortlist = shortlist->next;            }    return NULL ;}

4. 反转一个单链表。

struct ListNode* reverseList(struct ListNode* head){
       struct ListNode* cur = head;    struct ListNode* pre = NULL;    if(head == NULL) {
           return NULL;    }    if(head->next == NULL) {
           return head;    }    while(cur) {
           struct ListNode* tmp;        tmp = cur->next;        cur->next = pre;        pre = cur;        cur = tmp;    }    return pre;}

5. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
   如果有两个中间结点，则返回第二个中间结点。

struct ListNode* middleNode(struct ListNode* head){
       struct ListNode* slow,*fast;    slow = head;    fast = head;    if(fast == NULL) {
           return NULL;    }    while(fast != NULL && fast->next!=NULL) {
           slow = slow->next;        fast = fast->next->next;        }    return slow;    }

6. 输入一个链表，输出该链表中倒数第k个结点。

ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
           if(pListHead==NULL || k<=0){
               return NULL;        }        struct ListNode* p;        p = pListHead;        int count = 1;        while(p->next != NULL){
               count++;            p = p->next;                     }        if(k>count) {
               return NULL;        }        count = count-k;        p = pListHead;        while(count>0) {
               p = p->next;            count--;        }        return p;    }

7. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。

class Partition {
   public:    ListNode* partition(ListNode* pHead, int x) {
           // write code here        struct ListNode* small_head=NULL;        struct ListNode* big_head=NULL;        struct ListNode* small = small_head;        struct ListNode* big = big_head;        struct ListNode* head = pHead;        if(pHead == NULL) {
               return NULL;        }        if(head->next == NULL||head==NULL) {
               return head;        }                 while(head) {
               if(head->val
   
    next;                }                else{
                       small->next = head;                    head = head->next;                    small = small->next;                    small->next=NULL;                }            }            else{
                   if(big_head == NULL) {
                       big_head = head;                    big = big_head;                    head = head->next;                }                else{
                       big->next = head;                    head = head->next;                    big = big->next;                    big->next=NULL;                }            }        }        if(small_head == NULL) {
               return big_head;        }        if(big_head == NULL){
               return small_head;        }        if(small_head != NULL && big_head != NULL) {
               small->next = big_head;            return small_head;        }    }};
   

8. 删除链表中给定值 val 的所有节点

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     struct ListNode *next; * }; */struct ListNode* removeElements(struct ListNode* head, int val){
           struct ListNode *lastpoint, *p;	//链表为空	if (head == NULL)		return head;	//删除头节点			while (head->val == val)	{
   		if (head->next != NULL)			head = head->next;		else 			return NULL;	}	p = head;	//中间位置删除	if (head->next != NULL)	{
   		lastpoint = p;		p = p->next;	}	while (p->next != NULL)	{
   		if (p->val == val)		{
   			p = p->next;			lastpoint->next = p;		}		else		{
   			p = p->next;			lastpoint = lastpoint->next;		}	}	//尾节点删除	if (p->val == val)	{
   		lastpoint->next = NULL;	}	return head;}

9. 链表的回文结构

/*struct ListNode {    int val;    struct ListNode *next;    ListNode(int x) : val(x), next(NULL) {}};*/class PalindromeList {
   public:    bool chkPalindrome(ListNode* A) {
           // write code here        if(A==NULL)            return false;        else if(A->next==NULL)            return true;        //快慢指针找出中间节点        ListNode* quick=A;        ListNode* slow=A;        while(quick!=NULL&&quick->next!=NULL)        {
               quick=quick->next->next;            slow=slow->next;        }        //反转        ListNode* p=slow->next;        ListNode* p1=p->next;               while(p!=NULL)        {
               p->next=slow;            slow=p;            p=p1;            p1=p1->next;        }                 while(A!=slow)        {
               if((A->val)!=(slow->val))            {
                   return false;            }else{
                   if(A->next==slow)                {
                       return true;                }                A=A->next;                slow=slow->next;            }        }        return true;             }};

转载地址：http://whwzi.baihongyu.com/