不带哨兵位结点
不带哨兵位结点的意思是头结点head只是一个指向第一个结点的指针。带哨兵位结点时,则有一个表头结点,其数据域为NULL,指针域则指向第一个结点。
题目示例
示例 1
输入:head = [1,2,3,4,5]输出:[5,4,3,2,1]
示例2
输入:head = [1,2] 输出:[2,1]
示例3
输入:head = [] 输出:[]
题目思路
思路一
思路二
题目代码
思路一
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head) { if(head == NULL) return head; struct ListNode *note1,*note2,*note3; note1 = NULL; note2 = head; note3 = head->next; while(note2) { //翻转 note2->next = note1; //迭代往后 note1 = note2; note2 = note3; if(note3) note3 = note3->next; } return note1; }
思路二
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head) { struct ListNode *cur = head; struct ListNode*newhead = NULL; while(cur) { struct ListNode* next = cur->next; //头插 cur->next = newhead; newhead = cur; //迭代往后 cur = next; } return newhead; }
带有哨兵位结点
简单思路
带有哨兵位结点(带表头)的翻转也很简单,我们用思路二来写一下其中的一种解法。
先把头结点head用phead记录下来,把整个链表翻转之后,再用phead链接翻转之后的链表,返回phead即可。
代码
struct ListNode* reverseList(struct ListNode* head) { struct ListNode *phead = head; struct ListNode *cur = head; struct ListNode*newhead = NULL; while(cur) { struct ListNode* next = cur->next; //头插 cur->next = newhead; newhead = cur; //迭代往后 cur = next; } phead->next = newhead; return phead; }