每日一道小算法（七）[链表] 反转链表

女爷i 2023-06-30 01:51 103阅读 0赞

前言:  
链表在我们平常撸代码中经常使用，但是我们使用的并不是很熟悉，所以这一道题就是关于链表，让我们来熟悉一下吧。

### 题目描述 ###

输入一个链表，反转链表后，输出新链表的表头。

### 题目解析 ###

我们通过一个图来看一下一个链表和反转链表后的区别：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5Mzk3MTY1_size_16_color_FFFFFF_t_70]  
这一张图我们看出来了区别，那么就将一下反转流程：

*  当前节点a不为空，进入循环，先记录a的下一个节点位置next = b;再让a的指针指向pre
 *  移动pre和head的位置，正因为刚才记录了下一个节点的位置，所以该链表没有断，我们让head走向b的位置。
 *  当前节点为b不为空，先记录下一个节点的位置，让b指向pre的位置即a的位置，同时移动pre和head
 *  当前节点c不为空，记录下一个节点的位置，让c指向b，同时移动pre和head，此时head为空，跳出，返回pre

### 代码样例 ###

public class ListNode{ 
    
    	int val;
    	ListNode next = null;
    	public ListNode(int val)
    	{ 
    	 this.val = val;
    	}
    }
    
    public  class Solution{ 
    	public ListNode ReverseList(ListNode head)
    	{ 	
    		// 保存前一节点
    		ListNode pre = null;
    		//保存当前结点
    		ListNode pNode = head;
    		//保存下一结点
    		ListNode pNext = null;
    		while(pNode != null)
    		{ 
    			PNext = pNode.next;
    			pNode.next = pre;
    			pre = pNode;
    			PNode = pNext;
    		}
    		return pre;
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5Mzk3MTY1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020011322121470.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5Mzk3MTY1,size_16,color_FFFFFF,t_70