List

今天研究了一下markdown的語法才發(fā)現(xiàn)還有一種可以劃分出區(qū)域的方法。
鏈表是一種很常見的數(shù)據(jù)結(jié)構(gòu)童漩,那么我們就復習一下悦荒,使用C++現(xiàn)擼出一個linkedlist

#include <iostream>
using namespace std;

// Node類,封裝了一些常用的操作
template <typename T>
class Node{
public:
    //構(gòu)造函數(shù)
    Node();
    Node(T data);
    //析構(gòu)函數(shù)
    ~Node();

    void setData(T data);
    T getData();
    void setNext(Node<T> *next);
    Node* getNext();
    void printData();
private:
    T* m_tpData;
    Node<T> *m_tpNext;
}

template <typename T>
// 不帶參數(shù)的構(gòu)造函數(shù)
Node<T>::Node(){
    m_tpData = new T;
    m_tpNext = NULL;
}
// 帶參數(shù)的構(gòu)造函數(shù)
template<typename T>
Node<T>::Node<T data>{
    m_tpData = new T(data);
    m_tpNext = NULL;
}

template<typename T>
Node<T>::~Node(){
    delete m_tpData;
    m_tpNext = NULL;
}

template<typename T>
void Node<T>::setData(T data){
    *m_tpData = data;
}

template<typename T>
T Node<T>::getData(){
    return *m_tpData;
}

template<typename T>
void Node<T>::setNext(Node<T>* next){
    m_tpNext = next;
}

template <typename T>
Node<T>* Node<T>::getNext(){
    return m_tpNext;
}

template <typename T>
void Node<T>::printData(){
    cout << *m_tpData << endl;
}

template<typename T>
class LinkList{
public:
    LinkList();
    ~LinkList();
    bool isListEmpty();
    bool clearList();
    int getListLength();
    int getElemIndex(T &elem);
    bool getListElem(int index,T* elem);

    bool ListInsert(int index,T &elem);
    bool ListDelete(int index,T *elem);
    void ListPrint(void);
private:
    Node<T>* m_pList;
    int m_iLength;
}

template<typename T>
LinkList<T>::LinkList(){
    m_pList = new Node<T>;
    m_pList->setData(NULL);
    m_pList->setNext(NULL);
    m_iLength = 0;
}

template <typename T>
LinkList<T>::~LinkList(){
    Node<T> *nextNode = m_pList;
    while( nextNode -> getNext() != NULL){
        nextNode = m_pList -> getNext();
        delete m_pList;
        m_pList = nextNode;
    }
    delete m_pList;
    m_pList = NULL;
}

template <typename T>
bool LinkList<T>::isListEmpty(){
    return m_iLength == 0 ? true : false;
}

template <typename T>
bool LinkList<T>::clearList(){
    if(isListEmpty()){
        cout << "List is empty, clear fail." << endl;
    }
    // delete all nodes except the first one
    Node<T>* nowNode = m_pList->getNext();
    Node<T>* nextNode = m_pList->getNext();
    while(nextNode -> getNext() != NULL){
        nextNode = nowNode -> getNext();
        delete nowNode;
        nowNode = nextNode;
    }
    delete nowNode;

    // reset the list length
    m_iLength = 0;
    m_pList -> setNext(NULL);
    return true;
}

template <typename T>
int LinkList<T>::getListLength()
{
    return m_iLength;
}

template <typename T>
int LinkList<T>::getElemIndex(T &elem){
    // 獲取元素的索引
    Node<T>* tempNode = m_pList;
    for(int i=0; i<m_iLength; i++){
        tempNode = tempNode -> getNext();
        if( tempNode-> getData() == elem ) return i;
    }
    // 沒有找到
    return -1;
}

template <typename T>
bool LinkList<T>::getListElem(int index,T* elem){
        if( index < 0 || index >= m_iLength){
            return false;
        }

        Node<T>* tempNode = m_pList;
        for( int i=0; i<index; i++){
            tempNode = tempNode -> getNext();
        }
        *ele = tempNode -> getData();
        return true;
}


Leetcode上也有許多與鏈表相關的問題,我們來一一擊破

Remove Nth Node From End of List

Given a linked list, remove the n-th node from the end of list and return its head.

Example:
Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

這道題目是典型的雙指針問題居触,我們只要設置兩個指針就很容易完成。

eg:
array = {1, 2, 3, 4, 5, 6} n = 2 
initial phase
array           1 2 3 4 5 6
pre             ^       
tempNode        ^

offset tempNode  n steps
array           1 2 3 4 5 6
pre             ^       
tempNode            ^

both pointers start to move forward until tempNode meets the end
array           1 2 3 4 5 6
pre                   ^       
tempNode                  ^

do pre->next = pre->next->next to delete the element 

array           1 2 3 4 6
pre                     ^       
tempNode                ^

代碼如下, 要注意一下邊界條件的判斷

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if (!head->next) return NULL;
        // baecause n is always valid, so ignore the judge
        ListNode* tempNode = head, *pre = head;
        // offset tempNode 
        for(int i=0; i<n; i++){
            tempNode = tempNode -> next;
        }
        // 如果已經(jīng)移到NULL上
        if ( !tempNode ) return head->next;
        // go through the list together
        while( tempNode  != NULL ){
            if( tempNode -> next == NULL ){
                pre -> next= pre -> next -> next;
            }
                tempNode = tempNode -> next;
                pre = pre -> next;
          
        }
    return head;
    }
};

Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6

暴力的解法就是直接每次都對k個鏈表進行遍歷并且比較老赤,拿到當前鏈表頭上最小的數(shù)進行插入轮洋,這種方法時間復雜度應該是O(n^2),按照leetcode的尿性肯定會超時抬旺,所以就直接拋棄掉弊予。
下面可以想想一些典型的O(nlgn)的思路。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末开财,一起剝皮案震驚了整個濱河市汉柒,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌责鳍,老刑警劉巖碾褂,帶你破解...
    沈念sama閱讀 222,590評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異历葛,居然都是意外死亡斋扰,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,157評論 3 399
  • 文/潘曉璐 我一進店門啃洋,熙熙樓的掌柜王于貴愁眉苦臉地迎上來传货,“玉大人,你說我怎么就攤上這事宏娄∥试#” “怎么了?”我有些...
    開封第一講書人閱讀 169,301評論 0 362
  • 文/不壞的土叔 我叫張陵孵坚,是天一觀的道長粮宛。 經(jīng)常有香客問我,道長卖宠,這世上最難降的妖魔是什么巍杈? 我笑而不...
    開封第一講書人閱讀 60,078評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮扛伍,結(jié)果婚禮上筷畦,老公的妹妹穿的比我還像新娘。我一直安慰自己,他們只是感情好鳖宾,可當我...
    茶點故事閱讀 69,082評論 6 398
  • 文/花漫 我一把揭開白布吼砂。 她就那樣靜靜地躺著,像睡著了一般鼎文。 火紅的嫁衣襯著肌膚如雪渔肩。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,682評論 1 312
  • 那天拇惋,我揣著相機與錄音周偎,去河邊找鬼。 笑死撑帖,一個胖子當著我的面吹牛栏饮,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播磷仰,決...
    沈念sama閱讀 41,155評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼境蔼!你這毒婦竟也來了灶平?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,098評論 0 277
  • 序言:老撾萬榮一對情侶失蹤箍土,失蹤者是張志新(化名)和其女友劉穎逢享,沒想到半個月后,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體吴藻,經(jīng)...
    沈念sama閱讀 46,638評論 1 319
  • 正文 獨居荒郊野嶺守林人離奇死亡瞒爬,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,701評論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了沟堡。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片侧但。...
    茶點故事閱讀 40,852評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖航罗,靈堂內(nèi)的尸體忽然破棺而出禀横,到底是詐尸還是另有隱情,我是刑警寧澤粥血,帶...
    沈念sama閱讀 36,520評論 5 351
  • 正文 年R本政府宣布柏锄,位于F島的核電站,受9級特大地震影響复亏,放射性物質(zhì)發(fā)生泄漏趾娃。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,181評論 3 335
  • 文/蒙蒙 一缔御、第九天 我趴在偏房一處隱蔽的房頂上張望抬闷。 院中可真熱鬧,春花似錦耕突、人聲如沸饶氏。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,674評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽疹启。三九已至古程,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間喊崖,已是汗流浹背挣磨。 一陣腳步聲響...
    開封第一講書人閱讀 33,788評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留荤懂,地道東北人茁裙。 一個月前我還...
    沈念sama閱讀 49,279評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像节仿,于是被迫代替她去往敵國和親晤锥。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 45,851評論 2 361

推薦閱讀更多精彩內(nèi)容