單連結清單的建立、列印、删除和反轉

    單連結清單是一種非常重要的資料結構，它的優點是采用指針方式來增減結點，非常友善(它隻用改變指針的指向即可，不需要移動結點)；缺點是不能進行随機通路，隻能順着指針的方向進行順序通路。

    下面，介紹單例表的建立、列印和反轉。

    1、定義單連結清單

struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};
           

    2、建立單連結清單

ListNode* createLinkedList(int arr[], int n) {
	if (n == 0) {
		return NULL; 
	}

	ListNode* head = new ListNode(arr[0]);

	ListNode* curNode = head;
	for (int i = 1; i < n; i++) {
		curNode->next = new ListNode(arr[i]);
		curNode = curNode->next;
	}

	return head;
}

           

    3、列印單連結清單

void printLinkedList(ListNode* head) {
	ListNode* curNode = head;
	while (curNode != NULL) {
		cout << curNode->val << "->";
		curNode = curNode->next;
	}
	cout << "NULL" << endl;
}

           

    4、反轉單連結清單

    //該方法是采用頭插法，來反轉單連結清單

class Solution {
public:
	//不帶頭結點，反轉單連結清單(采用頭插法實作)
	ListNode* reverseList(ListNode* head) {
		ListNode* pre = NULL, *next=NULL;
		ListNode* cur = head;
		while (cur != NULL) {
			next = cur->next;
			cur->next = pre;
			pre = cur;
			cur = next;
		}
		return pre;
	}
};

           

    5、删除單連結清單

void deleteLinkdList(ListNode* head) {
	ListNode* curNode = head;
	while (curNode != NULL) {
		ListNode* delNode = curNode;
		curNode = curNode->next;
		delete delNode;
		delNode = NULL;
	}
}

           

   6、 完整代碼如下：

    //singleLink.cpp

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};

ListNode* createLinkedList(int arr[], int n) {
	if (n == 0) {
		return NULL; 
	}

	ListNode* head = new ListNode(arr[0]);

	ListNode* curNode = head;
	for (int i = 1; i < n; i++) {
		curNode->next = new ListNode(arr[i]);
		curNode = curNode->next;
	}

	return head;
}

void printLinkedList(ListNode* head) {
	ListNode* curNode = head;
	while (curNode != NULL) {
		cout << curNode->val << "->";
		curNode = curNode->next;
	}
	cout << "NULL" << endl;
}

void deleteLinkdList(ListNode* head) {
	ListNode* curNode = head;
	while (curNode != NULL) {
		ListNode* delNode = curNode;
		curNode = curNode->next;
		delete delNode;
		delNode = NULL;
	}
}

class Solution {
public:
	//不帶頭結點，反轉單連結清單(采用頭插法實作)
	ListNode* reverseList(ListNode* head) {
		ListNode* pre = NULL, *next=NULL;
		ListNode* cur = head;
		while (cur != NULL) {
			next = cur->next;
			cur->next = pre;
			pre = cur;
			cur = next;
		}
		return pre;
	}
};

int main() {
	int arr[] = { 1, 2, 3, 4, 5 };
	int n = sizeof(arr) / sizeof(int);
	ListNode* head = createLinkedList(arr, n);
	printLinkedList(head);

	ListNode* head2 = Solution().reverseList(head);
	printLinkedList(head2);

	deleteLinkdList(head2);

	system("pause");
	return 0;
}

           

    7、效果如下：

圖(1) 反轉單連結清單