重拾数据结构之链表-白红宇

1、Reverse a singly linked list.（反转链表）

input: 1->2->3->4->5->NULL  output: 5->4->3->2->1->NULL复制代码

Solution：

struct ListNode {    int val;    ListNode *next;    ListNode(int x) : val(x), next(NULL) {}};class Solution {public:    ListNode* reverseList(ListNode *head){        ListNode *preNode = NULL;        ListNode *curNode = head;        while ( curNode != NULL){            ListNode *nextNode = curNode->next;                       //change pointer direction            curNode->next = preNode;            preNode = curNode;            curNode = nextNode;        }        //pre will be the first node after reversing        return preNode;    }};复制代码

2、Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. （合并2个链表）

Input: 1->2->4, 1->3->4Output: 1->1->2->3->4->4复制代码

Solution：

struct ListNode {    int val;    ListNode *next;    ListNode(int x) : val(x), next(NULL) {}};class Solution {public:   ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {                if (l1 == NULL){                        return l2;                    }else if(l2 == NULL){                        return l1;                    }                ListNode *mergedNode = NULL;                if(l1->val < l2->val){                        mergedNode = l1;            mergedNode->next = mergeTwoLists(mergedNode->next,l2);                    }else{                        mergedNode = l2;            mergedNode->next = mergeTwoLists(l1, mergedNode->next);        }                return mergedNode;    }};复制代码

3、Given a linked list and a int value k, return the Kth node to tail in it.（找到链表的倒数第K个节点） Solution：

struct ListNode {    int val;    ListNode *next;    ListNode(int x) : val(x), next(NULL) {}};ListNode* FindKthToTail(ListNode* pListHead, unsigned int k){    if(pListHead == nullptr || k == 0)        return nullptr;        ListNode *pAhead = pListHead;    ListNode *pBehind = NULL;        for(unsigned int i = 0; i < k - 1; ++ i)    {        if(pAhead->next != NULL)            pAhead = pAhead->next;        else        {            return NULL;        }    }        pBehind = pListHead;        while(pAhead->next != NULL)    {        pAhead = pAhead->next;        pBehind = pBehind->next;    }        return pBehind;}复制代码

4、Remove Duplicates （删除重复节点）

Input: 1->1->2->3->3Output: 1->2->3复制代码

Solution：

struct ListNode {    int val;    ListNode *next;    ListNode(int x) : val(x), next(NULL) {}};ListNode* deleteDuplicates(ListNode* head){    ListNode *curNode = head;        while (curNode->next != NULL){                if (curNode->val == curNode->next->val){            			//delNode is the node to delete            ListNode *delNode = curNode->next;            curNode->next = delNode->next;            delete delNode;                    } else{                        curNode = curNode->next;                    }    }    return head;}复制代码

5、Given a linked list, determine if it has a cycle in it. （检测链表是否有环） Solution：

structstr  ListNode {   int val;   ListNode *next;   ListNode(int x) : val(x), next(NULL) {}};bool hasCycle(ListNode *head) {        ListNode* slowerNode = head;    ListNode* fasterNode = head;        while(slowerNode != NULL && fasterNode != NULL && fasterNode->next != NULL){                slowerNode = slowerNode->next;        fasterNode = fasterNode->next->next;                if(slowerNode == fasterNode){            return true;        }    }        return false;}复制代码

链表：http://www.cnblogs.com/QG-whz/p/5170147.html