大厂面试算法系列-如何实现链表的逆序(一)-原地逆序

小咪咪 2022-12-28 09:08 184阅读 0赞

> **题目描述**  
>   给定一个带有头节点的单向列表，将这个链表进行逆序。例如head->1->3->4->2,逆序之后变成head->2->4->3->1

**题目分析**  
  由于单链表的数据结构与数组的数据结构不同，对于链表来说每个节点都存在一个数据域和指针域，其中指针域存储的是下一个对象的地址。所以对于一个链表来说，要访问其中的任意节点，只能从头开始遍历，所以对于单链表来说查找的时间复杂度是O(n)。对于一个链表的操作，需要特别注意的就是对于指针的记录。不然就会丢失后续节点。

### 实现方案 ###

##### 原地反转 #####

实现思路：在遍历链表时，修改当前节点的指针域的指向，让其指向对应的前驱节点。做这样的操作，需要有一个指针变量来保存前驱结点的地址。另外，为了调整当前节点的指针域指向之后还能找到后继节点，还需要另外一个指针变量来保存后继节点的地址，在所有节点都做了同样的操作之后，就可以完成链表的逆序了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz_size_16_color_FFFFFF_t_70_pic_center]  
  如上图所示，当前已经遍历到的节点就是cur，在这个节点之前的所有节点都已经完成逆序了，所以，只需要将cur.next = pre 修改即可完成逆序。为了能够记录当前节点的后继节点，需要一个额外的指针next来保存后继节点的信息。一个节点的的逆序就是记性上面四个步骤。当前节点完成逆序之后，通过向后移动指针来对后续节点使用同样的方式来进行逆序操作。具体算法如下

public class Test{ 
    
    	/*对单链表进行逆序输入参数：head链表头节点*/
    	public static void Reverse(LNode head){ 
    		//判断链表是否为空
    		if(head==null||head.next==null){ 
    			return;
    		}
    		LNode pre = null;  // 当前结点
    		LNode cur = null;  // 当前结点
    		LNode next = null; // 后继结点
    
    		// 将链表的首节点变为尾节点 先进行指针变化
    		cur = head.next;
    		next = cur.next;
    		cur.next = null;
    		// 再进行节点变化
    		pre = cur;
    		cur = next;
    		// 使得当前遍历到的节点cur指向前驱节点
    		while (cur.next!=null){ 
    			// 如果当前节点的下一个节点不为空
    			// 将当前节点的下一个节点存储到next节点中
    			next = cur.next;
    			// 并且当前节点的下一个节点在指向前一个节点
    			cur.next = pre;
    			// 将当前节点节点变成前一个节点
    			pre = cur;
    			// 当前节点的下一个节点变成当前节点
    			cur = cur.next;
    			cur = next;
    		}
    		// 结点最后一个节点指向的是倒数第二个节点
    		cur.next = pre;
    		// 链表的头结点 指向原来链表的尾节点
    		head.next = cur;
    
    		public static void main(String[] args){ 
    			//链表的头结点
    			LNode head = new LNode();
    			head.next = null;
    			LNode tmp = null;
    			LNode cur = head;
    			//构造一个单链表
    			for(int i;i<8;i++){ 
    				tmp = new LNode();
    				tmp.data = i;
    				tmp.next = null;
    				cur.next = tmp;
    				cur = tmp;
    			}
    			System.out.print("逆序之前：")
    			for(cur = head.next;cur != null;cur = cur.next){ 
    				System.out.print(cur.data+" ");
    			}
    			System.out.print("逆序之后：")
    			Reverse(head);
    				for(cur = head.next;cur != null;cur = cur.next){ 
    				System.out.print(cur.data+" ");
    			}
    		}
    	}
    }

### 算法性能分析 ###

上面这种方式，对于链表的遍历只有一次，所以说从时间复杂度上来说是O(n)。但是在操作的过程中需要一个额外的变量来充当临时存储，所以说空间复杂度为O(1)。性能上算是比较高一点的了。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/5e45634e39ee4d25a4d427ee0b58d409.png