反转链表题目详解

浅浅的花香味﹌ 2022-12-13 01:19 151阅读 0赞

题目：输入一个链表，反转链表后，输出新链表的表头。  
![在这里插入图片描述][20201008202416423.png_pic_center]  
思想：  
1. 题目中所给的是单链表，想一想 反转后的样子：最后一个结点指向倒数第二个，倒数第二个指向倒数第三个，…第一个指向Null  
2.知道了反转后各个结点指向哪之后，就需要开始调整每个结点的next 指针  
3.这就需要把结点挨个从链表上摘下来，做调整；  
4.需要两个指针 pre 记录其前一个结点的位置，好让该节点的next指针指向前一个结点，但是在指向前一个结点前  
需要用一个指针P记录后一个结点的位置，  
注意 null；

/*public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    public class Solution {
        
        public ListNode ReverseList(ListNode head) {
        
              //初始化pre指针，用于记录当前结点的前一个结点地址
            ListNode pre = null;
            //初始化p指针，用于记录当前结点的下一个结点地址
            ListNode p = null;
            //head指向null时，循环终止。
            while(head != null){
        
                //先用p指针记录当前结点的下一个结点地址。
                p = head.next;
                //让被当前结点与链表断开并指向前一个结点pre。
                head.next = pre;
                //pre指针指向当前结点  结点后移
                pre = head;
                //head指向p(保存着原链表中head的下一个结点地址)
                head = p;
            }
            return pre;//当循环结束时,pre所指的就是反转链表的头结点
        }
    }

C语言实现

/**
     * struct ListNode {
     *	int val;
     *	struct ListNode *next;
     * };
     */
    
    /**
     * 
     * @param pHead ListNode类 
     * @return ListNode类
     */
    struct ListNode* ReverseList(struct ListNode* pHead ) {
        
          //定义三个指针 分别是 头结点  头结点之前  头结点之后
       struct   ListNode *pre =NULL;
       struct ListNode *p1=pHead;
       struct  ListNode *p2=NULL;
        while(p1!=NULL){
        
            p2=p1->next;//指定p2在p1的下一个结点
            p1->next=pre;//将p1与链表断开 指向pre;
            pre=p1;//pre 指向原来p1的位置
            p1=p2;// p1后移至 p2的 位置   
        }
        return pre;
    }

[20201008202416423.png_pic_center]: /images/20221123/23dbbbb5b11a419eab071733574e0470.png