【JAVA】每日两道编程题0930_LeetCode24 反转链表

待我称王封你为后i 2021-09-24 18:56 266阅读 0赞

# LeetCode24 反转链表 #

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

> 输入: 1->2->3->4->5->NULL  
> 输出: 5->4->3->2->1->NULL

*  标签：`栈`、`递归`、`双指针`
 *  思路一：`栈`  
    反转的特点：源串中最后遍历的元素是目标串最开始的元素。也就是后进先出特点，而栈刚好符合这个特点，所以用栈存储链表的值（push），然后一一取出(pop)。但这种解法的时间和空间复杂度均达不到标准。
 *  代码实现：

import java.util.Stack;
    
    //链表类定义。
    class ListNode{ 
        int val;
        ListNode next;
        ListNode(int x) { val = x;}
    }
    
    class ReverseList { 
        private static ListNode reverseList1(ListNode head) { 
        	//初始化栈stack
            Stack<ListNode> stack = new Stack<>();
            //遍历链表，将链表放入栈中
            while (head != null) { 
                stack.push(head);
                head = head.next;
            }
            //如果为空链表，返回null
            if(stack.isEmpty()) { 
                return null;
            }
            //取出栈顶元素作为head
            ListNode node = stack.pop();
            ListNode ans = node;
    		//取出栈中下一个元素，将链表反转，并将head更新。直到栈中没有元素
            while (!stack.isEmpty()) { 
                ListNode tmpNode = stack.pop();
                node.next = tmpNode;
                node = node.next;
            }
            //栈中没有元素时，head.next 置 null
            node.next = null;
            return ans;
        }
        
    	//测试用例
        public static void main(String[] args){ 
            int[] x = { 1,2,3,4,5,6};
            ListNode list = createLinkedList(x);
            printLinkedList(reverseList1(list));
        }
        
    	//将数组转化成链表
        private static ListNode createLinkedList(int[] x) { 
            if(x.length == 0) { 
                return null;
            }
            //初始化链表head节点，调用ListNode(int x)方法
            ListNode head = new ListNode(x[0]);
            ListNode current =  head;
            for(int i = 1; i < x.length; i++) { 
                current.next = new ListNode(x[i]);
                current = current.next;
            }
            return head;
        }
    	
    	//打印链表，格式为：6 -> 5 -> 4 -> NULL
        private static void printLinkedList(ListNode head) { 
            ListNode cur = head;
            while (cur != null) { 
                System.out.printf("%d ->", cur.val);
                cur = cur.next;
            }
            System.out.println("NULL");
        }
    }

*  结果输出

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

*  思路二：`双指针`
 *  代码实现

private static ListNode reverseList2(ListNode head) { 
            ListNode p = null;
            ListNode q = head;
            ListNode tmp = null;
            while (q != null) { 
                tmp = q.next;
                q.next = p;
                p = q;
                q = tmp;
            }
            return p;
        }

*  思路三：`递归`
 *  代码实现

//递归：栈的本质是递归，先进后出，栈顶是递归终止条件，栈的每一层是递归的方法体
        private static ListNode reverseList3(ListNode head) { 
            if (head == null || head.next == null) { 
                return head;
            }
            ListNode cur  = reverseList3(head.next);
            head.next.next = head;
            head.next = null;
            return cur;
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODg1MTk3MA_size_16_color_FFFFFF_t_70_pic_center]: /images/20210923/4db955944e084c979b3ac7c702b274cf.png