《刷题日记03》链表

浅浅的花香味﹌ 2024-03-17 13:06 59阅读 0赞

## 题目描述[力扣![icon-default.png_t_N5K3][]https://leetcode.cn/problems/LGjMqU/][icon-default.png_t_N5K3_https_leetcode.cn_problems_LGjMqU] ##

> **给定一个单链表 L 的头节点 head ，单链表 L 表示为：**
> 
>  **L0 → L1 → … → Ln-1 → Ln  
> 请将其重新排列后变为：**
> 
> **L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …**
> 
> **不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。**

## ![91d0c594bf544a2aa973f7ee59a4ed8d.png][] ##

![683a9789217648ddb5e6b2cdf84b47b8.png][]

## 解题思路1 ##

> **此种思路是自己看题解之前的思路：将后半段的链表进行反转并设置两个指针，在寻找中间结点时，采用了第一遍进行计数，第二遍采用结点遍历的方式，这种方法比较笨~，同时在反转链表方面，我选择了栈空间，但事实上不需要栈空间也能进行反转，且所需的空间复杂更低，而在当时的思路下，我也将前半段的结点信息存入了LinkedList中，也是比较笨~（可以直接遍历，优化的方法大家直接看第二种即可）**

## 代码实现1 ##

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public void reorderList(ListNode head) {
            //第一遍遍历查看链表中的个数
            int count=0;
            ListNode cur=head;
            while(cur!=null){
                count++;
                cur=cur.next;
            }
            //如果是1直接返回
            if(count==1){
                return;
            }
            //重新遍历放入栈中
            LinkedList<ListNode>stack1=new LinkedList<>();
            Stack<ListNode>stack2=new Stack<>();
            //重新遍历
            cur=head;
            for(int i=0;i<count/2;++i){
                //前半段入栈
                stack1.offer(cur);
                cur=cur.next;     
            }
            //后半段入栈
            while(cur!=null){
                stack2.push(cur);
                cur=cur.next;
            }
            stack1.pop();
            cur=head;
            //栈中取出
            while(stack1.size()!=0||!stack2.empty()){
                if(!stack2.empty()){
                    cur.next=stack2.pop();
                    cur=cur.next;
                }
                if(stack1.size()!=0){
                    cur.next=stack1.pop();
                    cur=cur.next;
                }
            }
            //最后解除循环
            cur.next=null;
        }
    }

## 解题思路2 ##

> **优化后的实现思路就比较明了了：通过前后指针进行遍历寻找中间结点，通过双指针进行里链表的反转，同时使用两个结点通过遍历就实现了链表的拼接，无需设计到额外的使用空间**

## 代码实现2 ##

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public void reorderList(ListNode head) {
            //分为三步对此进行求解 1.寻找中点2.翻转后半段链表3.进行合并
            ListNode mid=findMiddle(head);
            ListNode corret=mid.next;
            mid.next=null;
           ListNode head2= reverse(corret);
             merge(head,head2);
    
        }
        public ListNode findMiddle(ListNode head){
            if(head==null){
                return null;
            }
            ListNode slow=head;
            ListNode fast=head;
            while(fast.next!=null&&fast.next.next!=null){
                slow=slow.next;
                fast=fast.next.next;
            }
            return slow;
        }
        public ListNode reverse(ListNode head){
            if(head==null){
                return null;
            }
            ListNode cur=head;
            ListNode pre=null;
            //进行循环
            while(cur!=null){
                ListNode next=cur.next;
                cur.next=pre;
                pre=cur;
                cur=next;
            }
            return pre;
        }
        public ListNode merge(ListNode head1 ,ListNode head2){
            if(head1==null){
                return head2;
            }
            if(head2==null){
                return head1;
            }
            ListNode next1;
            ListNode next2;
            while(head1!=null&&head2!=null){
                next1=head1.next;
                next2=head2.next;;
                head1.next=head2;
                head1=next1;
                head2.next=head1;
                head2=next2;
            }
            return head1;
        }
    }

## 题目描述[力扣![icon-default.png_t_N5K3][]https://leetcode.cn/problems/LGjMqU/][icon-default.png_t_N5K3_https_leetcode.cn_problems_LGjMqU] ##

> **给定一个单链表 L 的头节点 head ，单链表 L 表示为：**
> 
>  **L0 → L1 → … → Ln-1 → Ln  
> 请将其重新排列后变为：**
> 
> **L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …**
> 
> **不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。**
> 
> **示例 1:**
> 
> **输入: head = \[1,2,3,4\]  
> 输出: \[1,4,2,3\]  
> 示例 2:**
> 
> **输入: head = \[1,2,3,4,5\]  
> 输出: \[1,5,2,4,3\]**  
> 
> 
> **提示：**
> 
> **链表的长度范围为 \[1, 5 \* 104\]  
> 1 <= node.val <= 1000**

## 解题思路 ##

> **该题目存在两种解题思路：1.将链表存放于数组中，利用双指针进行遍历判断2.使用递归思路进行解决，由于我对递归思路不太熟悉，所以这题使用递归思路来解决：定义一个中间结点从从前往后进行遍历与递归变更结点的进行照应，对比两个结点的值是否相等，相等递归方进行回溯，中键结点向下遍历，不相等直接返回FALSE即可**

## 实例代 ##

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        //定义从顶向下遍历的结点
        private ListNode tmpNode;
        public boolean isPalindrome(ListNode head) {
            tmpNode=head;
            return recursiveCheck(head);
        }
       boolean recursiveCheck(ListNode cur){
           if(cur!=null){
               if(!recursiveCheck(cur.next)){
                   return false;
               }
               if(tmpNode.val!=cur.val){
                   return false;
               }
               tmpNode=tmpNode.next;
           }
            return true;
        }
    }

[icon-default.png_t_N5K3]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/9b66692dacf44f5980555a70ff38c84b.png
[icon-default.png_t_N5K3_https_leetcode.cn_problems_LGjMqU]: https://leetcode.cn/problems/LGjMqU/
[91d0c594bf544a2aa973f7ee59a4ed8d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/92c4379dabd04a1ca0560d08a32865a6.png
[683a9789217648ddb5e6b2cdf84b47b8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/93ca536de9634f0e8391ff727d31e1b6.png