图解单向链表反转
单向链表反转需要用到三个指针:
prev:当前节点的前一个节点
cur:当前节点
next:当前节点的下一个节点
初始化:
prev = null , cur = head
首先将next赋值为当前节点的下一个节点, 即next= cur->next
为了实现链表的反转,需要将cur的next指针指向前一个节点,也就是prev节点:
此时就完成了链表中1节点的反转,为了使整个链表都反转,三个指针都需要往前移动一个单位:
重复上述过程直到cur=null时终止,即可完成整条链表的反转:
对应的code:
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
*/
void reverseLinkList(ListNode* head) {
ListNode* cur = head;
ListNode* prev = NULL;
while(cur!=NULL){
ListNode* next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
head = prev;
}