【题6 从尾到头打印链表】Java实现

一时失言乱红尘 2022-03-30 06:39 98阅读 0赞

**【题6 从尾到头打印链表】**  
**【题目】**  
输入一个链表的头节点，从头到尾反过来打印出每个结点的值。  
**先问：**  
是否允许修改输入的数据？  
**解决方案一：栈**  
首先遍历链表的节点后打印，典型的“后进先出”，可以使用栈来实现这种顺序。

*  遍历时候，每个结点放入栈中。
 *  遍历完整链表后，从栈顶开始逐个输出结点的值

**解决方案二：递归**  
栈的本质就是递归，直接使用递归的方式，打印一个节点的时候先打印它后面的节点，再打印该节点自身，实现反向打印  
**解决方案三：ArratList**  
遍历链表，把链表中的元素复制到ArrayList中，然后逆序打印ArrayList中的元素，由于ArrayList底层使用数组实现，所以用数组也是同样的原理  
**解决方案四：指针反转**  
前三种解决方案本身属于在打印链表的时候不修改链表本身结构，在允许修改链表结构的情况下可以把链表中的节点指针反转过来，改变链表方向，然后重新遍历打印改变方向后的链表。

**实现**

package ti5to2;
    
    import java.util.ArrayList;
    import java.util.Stack;
    
    class ListNode{
    	int val;
    	ListNode next = null;
    	
    	public ListNode(){
    	}
    	public ListNode(int value){
    		this.val = value;
    	}
    }
    public class No5PrintListFromTailToHead {
    	public static void main (String[] args){
    		ListNode node1 = new ListNode(1);
    		ListNode node2 = new ListNode(2);
    		ListNode node3 = new ListNode(3);
    		ListNode node4 = new ListNode(4);
    		ListNode node5 = null;
    		ListNode node6 = new ListNode(6);
    		ListNode node7 = new ListNode();
    		node1.next = node2;
    		node2.next = node3;
    		node3.next = node4;
    		printListFromTailToHead(node1);
    		printListFromTailToHead(node5);
    		printListFromTailToHead(node6);
    		printListFromTailToHead(node7);
    		//使用栈实现逆序打印链表
    		printListFromTailToHeadByStack(node1);
    		//使用递归实现逆序打印链表
    		printListFromTailToHead(node1);
    		//使用递归反转实现逆序打印
    		printListFromTailToHeadByReverseList(node1);
    		//使用ArrayList逆序打印链表
    		printListFromTailToHeadByArrayList(node1);
    	}
    	/*
    	 * 方案1：通过使用栈结构，遍历链表，把先遍历的节点的值推入栈中，遍历结束通过弹出栈内元素实现逆序打印
    	 */
    	public static void printListFromTailToHeadByStack(ListNode node){
    		Stack<Integer> stack = new Stack<Integer>();
    		while(node != null){
    			stack.push(node.val);
    			node = node.next;
    		}
    		while(!stack.isEmpty()){
    			System.out.println(stack.pop()+",");
    		}
    	}
    	/*
    	 * 2.递归法逆序打印链表
    	 */
    	public static void printListFromTailToHead(ListNode node){
    		if(node != null){
    			if(node.next != null){
    				printListFromTailToHead(node.next);
    			}
    			System.out.println(node.val+",");
    		}
    		else{
    			System.out.println("输入的链表为空");
    		}
    	}
    	/*
    	 * 3.使用ArrayList逆序打印链表
    	 */
    	public static void printListFromTailToHeadByReverseList(ListNode node){
    		if(node == null){
    			System.out.println("输入链表为null");
    		}
    		ArrayList<Integer> arrayList = new ArrayList<Integer>();
    		//解析：Stack<NestedInteger> stack = new Stack<NestedInteger>();
    		//<>代表泛型，Stack<NestedInteger>代表该Stack中只能放入NestedInteger类或者其子类的实例。
    		while(node != null){
    			arrayList.add(node.val);
    			node = node.next;
    		}
    		for(int i = arrayList.size()-1;i >= 0;i--){
    			System.out.println(arrayList.get(i)+",");
    		}
    	}
    	/*
    	 * 4.递归反转链表后遍历打印
    	 */
    	public static void printListFromTailToHeadByArrayList(ListNode node){
    		ListNode reversedNode = reverse(node);
    		while(reversedNode != null){
    			System.out.println(reversedNode.val+",");
    			reversedNode = reversedNode.next;
    		}
    	}
    	private static ListNode reverse(ListNode head){
    		if(head.next == null){
    			return head;
    		}
    		
    		ListNode reversedListNode = reverse(head.next);
    		head.next.next = head;
    		head.next = null;
    		return reversedListNode;
    	}
    
    }

**输出结果**

4,
    3,
    2,
    1,
    输入的链表为空
    6,
    0,
    4,
    3,
    2,
    1,
    4,
    3,
    2,
    1,
    4,
    3,
    2,
    1,
    4,
    3,
    2,
    1,

**注**  
**1.结点4 5 6 7**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]  
**2.方法4 指针反转**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]

**3.单链表反转**  
如何把一个单链表进行反转？  
**方法1：**  
将单链表储存为数组，然后按照数组的索引逆序进行反转。**浪费空间**  
**方法2：**  
使用3个指针遍历单链表，逐个链接点进行反转。  
**使用p和q两个指针配合工作，使得两个节点间的指向反向，同时用r记录剩下的链表。**

p = head;
    q = head->next;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 2]

head->next = NULL;

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 3][]  
现在进入循环体，这是第一次循环。

r = q->next;
    q->next = p;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 4]

p = q;
    q =r;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 5]  
第二次循环。

r = q->next

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 6]

q->next = p;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 7]

p = q;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 8]

q = r

![在这里插入图片描述][20190105083821483.png]  
。。。。。。

**方法3：**  
从第2个节点到第N个节点，依次逐节点插入到第1个节点(head节点)之后，最后将第一个节点挪到新表的表尾。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 9]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 10]

方法是：对于一条链表，从第2个节点到第N个节点，依次逐节点插入到第1个节点(head节点)之后，(N-1)次这样的操作结束之后将第1个节点挪到新表的表尾即可。

**方法4: 递归**  
(相信我们都熟悉的一点是，对于树的大部分问题，基本可以考虑用递归来解决。但是我们不太熟悉的一点是，对于单链表的一些问题，也可以使用递归。可以认为单链表是一颗永远只有左(右)子树的树，因此可以考虑用递归来解决。或者说，因为单链表本身的结构也有自相似的特点，所以可以考虑用递归来解决)  
现在需要把A->B->C->D进行反转，  
可以先假设B->C->D已经反转好，已经成为了D->C->B,那么接下来要做的事情就是将D->C->B看成一个整体，让这个整体的next指向A，所以问题转化了反转B->C->D。那么，  
可以先假设C->D已经反转好，已经成为了D->C,那么接下来要做的事情就是将D->C看成一个整体，让这个整体的next指向B，所以问题转化了反转C->D。那么，  
可以先假设D(其实是D->NULL)已经反转好，已经成为了D(其实是head->D),那么接下来要做的事情就是将D(其实是head->D)看成一个整体，让这个整体的next指向C，所以问题转化了反转D。

单向链表经常被设计成面试题  
面试题6：从头到尾打印链表  
面试题18：删除链表的节点  
面试题22：链表中倒数第k个节点  
面试题24：反转链表  
面试题25：合并两个排序的链表  
面试题52：两个链表的第一个公共节点  
等

参考  
1.《剑指offer》  
2.[https://www.cnblogs.com/gl-developer/p/6438311.html][https_www.cnblogs.com_gl-developer_p_6438311.html]  
3.[https://www.weiweiblog.cn/printlistfromtailtohead/][https_www.weiweiblog.cn_printlistfromtailtohead]  
4.[https://www.cnblogs.com/mafeng/p/7149980.html][https_www.cnblogs.com_mafeng_p_7149980.html]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]: /images/20220330/472ab2beb6144a4a9158c3c99afdca81.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]: /images/20220330/39dc7133ab1b48309a17d8d90446669d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 2]: /images/20220330/39b08decddb74c54914d036933e9641d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 3]: /images/20220330/3df9cf16e1794c9aaa674d2f068fc432.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 4]: /images/20220330/ea2cb77328234d60adc15c2e6235fab4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 5]: /images/20220330/27bd1a54abd344319852cb07a8e904bb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 6]: /images/20220330/f049a104c72a4f60b731ff84dd0a0549.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 7]: /images/20220330/4d6ec9c0dc5b4100b828ceda027b05e1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 8]: /images/20220330/fdcd528cc5b047d59e17f65d49ac03a1.png
[20190105083821483.png]: /images/20220330/305cf39cdc7b4857af044e2839217fb8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 9]: /images/20220330/db854563db1b4ac3bf6ccb1b49388e9a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 10]: /images/20220330/43a678579b704809a1c608b939342a78.png
[https_www.cnblogs.com_gl-developer_p_6438311.html]: https://www.cnblogs.com/gl-developer/p/6438311.html
[https_www.weiweiblog.cn_printlistfromtailtohead]: https://www.weiweiblog.cn/printlistfromtailtohead/
[https_www.cnblogs.com_mafeng_p_7149980.html]: https://www.cnblogs.com/mafeng/p/7149980.html