今天研究了一下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)的思路。