關于stl中list的reverse操作詳解

reverse()用于反轉容器中的元素

template<class T>
	void list<T>::reverse() {
		if (empty() || head.p->next = tail.p)
			return;
		auto curNode = head.p;
		head.p = tail.p->next;
		head.p->prev = nullptr;
		do {
			auto nextNode = curNode->next;
			curNode->next = head.p->next;
			head.p->next_prev = curNode;
			head.p->next = curNode;
			curNode->prev = head.p;
			curNode = nextNode;
		}while(curNode!=head.p)
	}
           

首先看一下list原樣與反轉之後的新的list

下面描述反轉操作

第一步：

auto curNode = head.p;
head.p = tail.p->next;
head.p->prev = nullptr;
           

curNode代表準備移動的連結清單節點，整體的思路是将原始連結清單中的4節點作為頭節點，然後将原始list中的剩餘節點依次插入4節點的後面

第二步：

curNode->next = head.p->next;
head.p->next->prev = curNode;
head.p->next = curNode;
curNode->prev = head.p;
           

将1節點插入4節點的後面，并進行prev、next的連接配接

第三步：

curNode->next = head.p->next;
head.p->next->prev = curNode;
head.p->next = curNode;
curNode->prev = head.p;
curNode = nextNode;
           

将先前儲存好的2節點作為下一個插入的節點，重複第二步，在4節點之後進行插入

第四步：

重複第三步