public class Solution { public ListNode ReverseList(ListNode head) { if(head==null) return null; //head为当前节点,如果当前节点为空的话,那就什么也不做,直接返回null; ListNode pre = null; ListNode next = null; //当前节点是head,pre为当前节点的前一节点,next为当前节点的下一节点 //需要pre和next的目的是让当前节点从pre->head->next1->next2变成pre<-head next1->next2 //即pre让节点可以反转所指方向,但反转之后如果不用next节点保存next1节点的话,此单链表就此断开了 //所以需要用到pre和next两个节点 //1->2->3->4->5 //1<-2<-3 4->5 while(head!=null){ //做循环,如果当前节点不为空的话,始终执行此循环,此循环的目的就是让当前节点从指向next到指向pre //如此就可以做到反转链表的效果 //先用next保存head的下一个节点的信息,保证单链表不会因为失去head节点的原next节点而就此断裂 next = head.next; //保存完next,就可以让head从指向next变成指向pre了,代码如下 head.next = pre; //head指向pre后,就继续依次反转下一个节点 //让pre,head,next依次向后移动一个节点,继续下一次的指针反转 pre = head; head = next; } //如果head为null的时候,pre就为最后一个节点了,但是链表已经反转完毕,pre就是反转后链表的第一个节点 //直接输出pre就是我们想要得到的反转后的链表 return pre; } }
//第一种方法是:非递归方法 /* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* ReverseList(ListNode* pHead) { if(pHead==NULL) return NULL;//注意程序鲁棒性 ListNode* pNode=pHead;//当前指针 ListNode* pReverseHead=NULL;//新链表的头指针 ListNode* pPrev=NULL;//当前指针的前一个结点 while(pNode!=NULL){//当前结点不为空时才执行 ListNode* pNext=pNode->next;//链断开之前一定要保存断开位置后边的结点 if(pNext==NULL)//当pNext为空时,说明当前结点为尾节点 pReverseHead=pNode; pNode->next=pPrev;//指针反转 pPrev=pNode; pNode=pNext; } return pReverseHead; } } //第二种方法是:递归方法 /* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* ReverseList(ListNode* pHead) { //如果链表为空或者链表中只有一个元素 if(pHead==NULL||pHead->next==NULL) return pHead; //先反转后面的链表,走到链表的末端结点 ListNode* pReverseNode=ReverseList(pHead->next); //再将当前节点设置为后面节点的后续节点 pHead->next->next=pHead; pHead->next=NULL; return pReverseNode; } };
注意关于链表问题的常见注意点的思考:
1、如果输入的头结点是 NULL,或者整个链表只有一个结点的时候
2、链表断裂的考虑
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # 返回ListNode def ReverseList(self, pHead): # write code here if pHead==None or pHead.next==None: return pHead pre = None cur = pHead while cur!=None: tmp = cur.next cur.next = pre pre = cur cur = tmp return pre
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* ReverseList(ListNode* pHead) { ListNode* h = NULL; for(ListNode* p = pHead; p; ){ ListNode* tmp = p -> next; p -> next = h; h = p; p = tmp; } return h; } };
输入一个链表,反转链表后,输出新链表的表头。
一开始学的时候看的答案就是这个方法,显然是要比递归好的,但是如果不理解的话,光靠背很容易出错,并且也不大背的上,如今重温这道题,其实是很简单的,我们下面用图示来阐述。
主要的思想是用两个指针,其中newHead
指向的是反转成功的链表的头部,currentHead
指向的是还没有反转的链表的头部:
初始状态是newHead
指向null
,currentHead
指向的是第一个元素,一直往后遍历直到newHead
指向最后一个元素为止:
下面展示的是其中某个时间点的指向细节:
理解了上面的图示,程序就呼之欲出了。
public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode newHead = null;
ListNode currentHead = head;
if(head == null || head.next == null){
return head;
}
while(currentHead != null){
ListNode next = currentHead.next;
currentHead.next = newHead;
newHead = currentHead;
currentHead = next;
}
return newHead;
}
}
// 这里采用一种递归的方式,从链表节点的尾部进行反转指针即可。仔细体会,递归的简练。
代码如下:
public class Solution {
public ListNode ReverseList(ListNode head) {
if(head == null || head.next == null) {
return head;
}
ListNode preNode = ReverseList(head.next);
head.next.next = head;
head.next = null;
return preNode;
}
}
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # 返回ListNode def ReverseList(self, pHead): # write code here if not pHead or not pHead.next: return pHead last = None while pHead: tmp = pHead.next pHead.next = last last = pHead pHead = tmp return last
class Solution { public: ListNode* ReverseList(ListNode* pHead) { if (pHead == NULL) return NULL; if (pHead->next == NULL) return pHead; ListNode *pBefore = pHead, *p = pHead->next, *pAfter = p->next; while (pAfter) { p->next = pBefore; // reverse pBefore = p; p = pAfter; pAfter = pAfter->next; } p->next = pBefore; pHead->next = NULL; return p; } };
class Solution { public: ListNode* ReverseList(ListNode* pHead) { if (pHead == NULL) return NULL; ListNode* head = pHead; pHead = pHead->next; head->next = NULL; while (pHead) { ListNode *next = pHead->next; pHead->next = head; head = pHead; pHead = next; } return head; } };
/*struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* ReverseList(ListNode* pHead) { if(pHead==NULL||pHead->next == NULL) { return pHead; } ListNode * p=pHead; ListNode * newHead; stack<ListNode *> stack1; while(p->next!=NULL) { stack1.push(p); p=p->next; } newHead = p; while(!stack1.empty()) { p->next=stack1.top(); p=p->next; stack1.pop(); } p->next=NULL; return newHead; } };
反转链表是很基本的操作
class ListNode {
int val;
ListNode
next = null;
ListNode(int val) {
this.val = val;
}
}
public class Solution {
public ListNode
ReverseList(ListNode head) {
ListNode cur=head;
ListNode pre=null;
ListNode next=null;
while(cur!=null)
{
next=cur.next;
cur.next=pre;
pre=cur;
cur=next;
}
return pre;
}
}
需要三个指针相互赋值移动完成
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
if(pHead == NULL) return NULL;
ListNode *last = pHead, *nex = pHead->next, *cur = nex;
last->next = NULL; //头结点指向NULL
while(cur != NULL){
nex = cur->next;
cur->next = last;
last = cur;
cur = nex;
}
return last;
}
};
/* * 使用Java栈的方式,这里的注意点是原来的头结点的next需要置为null,否则会导致遍历时无限循环,导致超时 */ public ListNode ReverseList(ListNode head) { if (head == null) return null; Stack<ListNode> stack = new Stack<ListNode>(); ListNode temp = head; do { stack.push(temp); temp = temp.next; } while (temp != null); //关键在于这里,原来的头结点的next要置为空,否则导致遍历时无限循环 head.next = null; ListNode root = stack.pop(); ListNode node = root; while (!stack.isEmpty()) { node.next = stack.pop(); node = node.next; } return root; }
class Solution { public: ListNode* ReverseList(ListNode* pHead) { if(pHead == NULL || pHead->next == NULL) { return pHead; } ListNode* last=NULL; ListNode* now=NULL; while(pHead){ now=pHead; //问题就在这,两个指针指向同一个地址,now改变,pHead就变了 now->next=last; last=now; pHead=pHead->next; } return now; //-------------------------------------------上面的不行,下面的可以 ListNode* next=NULL; while(pHead){ next=pHead->next;//其实三个指针指向三个地方 pHead->next=last; last=pHead; pHead=next; } return last; } };
class Solution { public: ListNode* ReverseList(ListNode* pHead) { if (pHead == NULL || pHead->next == NULL) return pHead; ListNode *pre = pHead; ListNode *cur = pHead->next; while (cur) { ListNode *post = cur->next; cur->next = pre; pre = cur; cur = post; } pHead->next = NULL; return pre; } };
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode ReverseList(ListNode head) { if (head == null) return null; if (head.next == null) return head; ListNode pPre = null; ListNode p = head; ListNode pNext = head.next; ListNode newHead = null; while (p != null) { pNext = p.next;//一定要记录下来后面的节点 if (pNext == null) newHead = p; p.next = pPre;//这里的方向已经转变 pPre = p; p = pNext;//将保存的后面的节点作为下一次循环的p } return newHead; } }
/**
* 反转链表
* 题目描述
* 输入一个链表,反转链表后,输出链表的所有元素。
*
* @author shijiacheng
* @date 2018/2/23
*/
public class ReverseListSolution {
/**
* 依次遍历所有节点,将所有节点的next指向前一个节点
*/
public ListNode ReverseList(ListNode head) {
ListNode pre = null;
ListNode next = null;
while (head != null) {
next = head.next;//持有下一个节点的引用
head.next = pre;//将当前节点对下一个节点的引用指向前一个节点
pre = head;//将前一个节点指向当前节点
head = next;//将当前节点指向下一个节点
}
return pre;
}
}
/*function ListNode(x){ this.val = x; this.next = null; }*/ function ReverseList(pHead) { // write code here if(!pHead) return null; var pre = pHead; // 定义上一个节点 var head = pHead; // 定义当前节点 while(head) { // 如果存在当前节点 // 将当前节点的下一个节点用next保存 let next = head.next; // 让当前节点指向next,变为指向pre(上一个节点) head.next = pre; // 上面两步实现了一节链表的反转,下面,将pre,head,next依次后移一位,再次反转 pre = head; head = next; } // 将反转后的链表尾部(对应开始未反转链表的头部)设为null pHead.next = null; // 返回新链表的表头 return pre; }