牛客在线编程101-01反转链表

左手的ㄟ右手 2023-10-04 19:31 59阅读 0赞

**题目：**  
描述：给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： 0\\leq n\\leq10000≤n≤1000  
要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n) 。

如当输入链表\{1,2,3\}时，  
经反转后，原链表变为\{3,2,1\}，所以对应的输出为\{3,2,1\}。  
以上转换过程如下图所示：

示例1  
输入：  
\{1,2,3\}  
返回值：  
\{3,2,1\}  
说明：  
空链表则输出空

解题思路：  
方法1：看到反转联想到栈，通过栈的特性可以实现反转  
代码为：

/*
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    import java.util.*;
    public class Solution {
        
        public ListNode ReverseList(ListNode head) {
        
            if (head == null || head.next == null) {
        
                return head;
            }
    
            Stack<ListNode> stack = new Stack<>();
            ListNode tmp = head;
            while(tmp != null) {
        
                stack.push(tmp);
                tmp = tmp.next;
            }
    
            ListNode newHead = stack.pop();
            tmp = newHead;
            while(!stack.isEmpty()) {
        
                tmp.next = stack.pop();
                tmp = tmp.next;
            }
            tmp.next = null;
    
            return newHead;
        }
    }

方法2：将链表拆开，重新链接。遍历链表，将遍历过的节点按照相反的顺序组合成新链表，新链表的最后的节点则为新链表的头结点

/*
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    import java.util.*;
    public class Solution {
        
        public ListNode ReverseList(ListNode head) {
        
            ListNode pre = null;
            ListNode next = null;
            while (head != null) {
        
                next = head.next;
                head.next = pre;
                pre = head;
                head = next;
            }
            return pre;
        }
    }