【题24 反转链表】

ゞ浴缸里的玫瑰 2022-03-25 06:37 185阅读 0赞

**【题24 反转链表】**  
**【题目】**  
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

**分析：**  
为了正确地反转一个链表，需要调整链表中指针的方向，借图形直观分析  
![在这里插入图片描述][20190119091641286.png]  
图a中h，i，j是三个相邻节点，经过若干操作，把节点h之前的指针调整完毕，这些节点的m\_pNext都指向前一个节点，把i的m\_pNext指向h，如图b。为了避免链表在节点i处断开，需在调整节点i的m\_pNext前，把节点j保存下来

**定义3个指针**  
分别指向当前遍历到的节点，它的前一个节点以及后一个节点。

**常见的3个问题：**  
1． 输入的链表头指针为空或整个链表只有一个节点时，程序立即崩溃  
2． 反转后的链表出现断裂  
3． 返回的反转之后的头节点不是原始链表的尾结点

**发现的好办法：**  
提前想好测试用例

**以下测试用例进行功能测试**：

1.  输入的链表头指针是空
2.  输入的链表只有一个节点
3.  输入的链表有多个节点

**实现**

package ti24;
    
    //反转链表
    
    class ListNode{
    	int value;
    	ListNode next;
    }
    public class Lianxi {
    	public static void main(String[] args) {
    		Lianxi lx = new Lianxi();
    		
    		ListNode head = new ListNode();
    		ListNode temp1 = new ListNode();
    		ListNode temp2 = new ListNode();
    		ListNode temp3 = new ListNode();
    		ListNode temp4 = new ListNode();
    		ListNode temp5 = new ListNode();
    		
    		head.value = 1;
    		temp1.value = 2;
    		temp2.value = 3;
    		temp3.value = 4;
    		temp4.value = 5;
    		temp5.value = 6;
    		
    		head.next = temp1;
    		temp1.next = temp2;
    		temp2.next = temp3;
    		temp3.next = temp4;
    		temp4.next = temp5;
    		temp5.next = null;
    		
    		System.out.println("反转前：");
    		lx.printList(head);
    		//执行反转操作
    		System.out.println();
    		System.out.println("反转后");
    		ListNode reverseHead = lx.reverse(head);
    		lx.printList(reverseHead);
    	}
    	
    	public void printList(ListNode head){
    		while(head != null){
    			System.out.print(head.value+" ");
    			head = head.next;
    		}
    	}
    	
    	public ListNode reverse(ListNode head){
    		//如果输入的链表为空，就直接返回空
    		if(head == null){
    			return null;
    		}
    		
    		//如果输入的链表只有一个节点，即，头节点，则直接返回该节点
    		if(head.next == null){
    			return head;
    		}
    		
    		//定义反转后链表的头节点
    		ListNode revHead = null;
    		//当前节点
    		ListNode curNode = head;
    		
    		while(curNode != null){
    			ListNode tmpNode = curNode.next;//记录下当前节点的下一个节点
    			curNode.next = revHead;//将当前节点的下一个节点反转指向反转链表的头节点
    			revHead = curNode;
    			curNode = tmpNode;
    		}
    		return revHead;
    	}
    
    }

**使用递归**

public static ListNode reverse(ListNode head) {
            // 参数校验
            if (head == null || head.next == null) {
                return head;
            }
    
            ListNode secondElem = head.next;
            head.next = null;
            ListNode revHead = reverse(secondElem);
            secondElem.next = head;
            return revHead;
        }

**注释**  
图解代码

while(curNode != null){
    			ListNode tmpNode = curNode.next;//记录下当前节点的下一个节点
    			curNode.next = revHead;//将当前节点的下一个节点反转指向反转链表的头节点
    			revHead = curNode;
    			curNode = tmpNode;
    		}
    		return revHead;
    	}

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

参考：  
1.《剑指offer》  
2.[https://blog.csdn.net/weixin\_37672169/article/details/80167895][https_blog.csdn.net_weixin_37672169_article_details_80167895]

[20190119091641286.png]: /images/20220325/5e01798bac854b0f8d90f3609ede2628.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]: /images/20220325/61f386df0e464d48918264c0fd977e14.png
[https_blog.csdn.net_weixin_37672169_article_details_80167895]: https://blog.csdn.net/weixin_37672169/article/details/80167895