链表基础+剑指offer6题

自己实现的链表

//
//  main.cpp
//  链表基础
//
//  Created by 张传奇 on 2018/8/1.
//  Copyright © 2018年 张传奇. All rights reserved.
//

#include <iostream>

struct ListNode {
    int m_nValue;
    ListNode * m_pNext;
};

void AddToTail(ListNode ** pHead,int value) {
    ListNode * pNew = new ListNode();
    pNew->m_nValue = value;
    pNew->m_pNext = nullptr;
    
    if (*pHead == nullptr) {
        *pHead = pNew;
    }else
    {
        ListNode * pNode = *pHead;
        
        while (pNode->m_pNext != nullptr) {
            pNode = pNode->m_pNext;
        }
        pNode->m_pNext = pNew;
    }
    
    
}

void InsertNode(ListNode ** pHead,int index,int value) {
    
    int tempIndex = 0;
    ListNode * pNode = *pHead;
    while (pNode->m_pNext != nullptr && tempIndex < index-1) {
        pNode = pNode->m_pNext;
    }
    
    ListNode * pNew = new ListNode();
    pNew->m_nValue = value;
    pNew->m_pNext = pNode->m_pNext;
    pNode->m_pNext = pNew;
    
    
    
}



void removeNode(ListNode ** pHead,int value) {
    if (pHead == nullptr || *pHead == nullptr) {
        return;
    }
    
    ListNode * pToBeDeleted = nullptr;
    if ((*pHead)->m_nValue == value) {
        pToBeDeleted = *pHead;
        *pHead = (*pHead)->m_pNext;
    }
    else
    {
        ListNode * pNode = *pHead;
        
        while (pNode->m_pNext != nullptr && pNode->m_pNext->m_nValue != value) {
            pNode = pNode->m_pNext;
        }
        
        if (pNode->m_pNext != nullptr && pNode->m_pNext->m_nValue == value) {
            pToBeDeleted = pNode->m_pNext;
            pNode->m_pNext = pNode->m_pNext->m_pNext;
        }
        
        
        
    }
    
    if (pToBeDeleted != nullptr) {
        delete pToBeDeleted;
        pToBeDeleted = nullptr;
    }
    
    
}

void NodePrint(ListNode ** pHead) {
    ListNode * pNode = *pHead;
    while (pNode != nullptr) {
        std::cout<<pNode->m_nValue;
        std::cout<<" ";
        pNode=pNode->m_pNext;
    }
    std::cout<<"\n";
}

int searchNode(ListNode ** pHead,int value) {
    if (pHead == nullptr || *pHead == nullptr) {
        return 0;
    }
    int index = 1;
      ListNode * pNode = *pHead;
    while ( pNode != nullptr && pNode->m_nValue != value) {
        pNode = pNode->m_pNext;
        index ++;
    }
    if (pNode->m_nValue != value) {
        return 0;
    }
    
    
    return index;
}
int getLength(ListNode ** pHead) {
    if (pHead == nullptr || *pHead == nullptr) {
        return 0;
    }
    int index = 0;
     ListNode * pNode = *pHead;
    while ( pNode != nullptr ) {
        pNode = pNode->m_pNext;
        index ++;
    }
    
    return index;
    
}
int main(int argc, const char * argv[]) {
    // insert code here...
    
    ListNode * pHead = new ListNode();
    pHead->m_nValue = 1;
    pHead->m_pNext = nullptr;
    std::cout<<getLength(&pHead);
    std::cout<<"\n";
    AddToTail(&pHead, 5);
    AddToTail(&pHead, 8);
    AddToTail(&pHead, 3);
    AddToTail(&pHead, 0);
    AddToTail(&pHead, 1);
    AddToTail(&pHead, 6);
    NodePrint(&pHead);
    removeNode(&pHead, 0);
    removeNode(&pHead, 1);
    NodePrint(&pHead);
    
    std::cout<<searchNode(&pHead, 1);
    std::cout<<"\n";
    std::cout<<getLength(&pHead);
    std::cout<<"\n";


    return 0;
}

题目：输入一个链表的头结点，从头到尾反过来打印每个节点的值

一：把链表遍历一遍放入一个栈或者数组里，然后如果放到栈里就不断的出栈，如果数组从尾开始打印就好

//非递归实现
void PrintListReversingly_Iteratively(ListNode * pHead) {
    if (pHead == nullptr ) {
        return ;
    }
    std::stack<ListNode *> nodes;
    
    ListNode * pNode = pHead;
    while (pNode != nullptr) {
        nodes.push(pNode);
        pNode = pNode->m_pNext;
    }
    
    while (!nodes.empty()) {
        pNode = nodes.top();
        std::cout<<pNode->m_nValue;
        std::cout<<" ";
        nodes.pop();
    }
    std::cout<<"\n";
    
}

二：用递归的方法先递归后面的节点，再输出该节点，就可以反向打印了

//递归实现
void PrintListReversingly_Recurisively(ListNode * pHead) {
    if (pHead == nullptr ) {
        return ;
    }
    
    if (pHead->m_pNext != nullptr) {
        PrintListReversingly_Recurisively(pHead->m_pNext);
    }
    std::cout<<pHead->m_nValue;
    std::cout<<" ";
}