重拾数据结构之链表

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->4
Output: 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->3
Output: 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;
}

6、如何快速找到单向链表的中间节点

ListNode * GetMiddleNode ( iNode *head ) 
{ 
    iNode *p1 = head; 
    iNode *p2 = p1; 
    while( p2 ) 
    { 
        p2 = p2->next; 
        if(p2！=NULL) 
        { 
            p2 = p2->next; 
            p1=p1->next; 
        } 
    } 
    return p1; 
}

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