【LeetCode】链表问题：双指针或回溯

冷不防 2022-10-29 09:11 144阅读 0赞

### 双指针或回溯 ###

*  对于链表中要拿到后几个元素的问题，一定是双指针
 *  对于链表前几个元素要使用后面的元素，那么可以递归回溯

#### [19. 删除链表的倒数第 N 个结点][19. _ N] ####

难度中等1199收藏分享切换为英文接收动态反馈

给你一个链表，删除链表的倒数第 `n` 个结点，并且返回链表的头结点。

\*\*进阶：\*\*你能尝试使用一趟扫描实现吗？

**示例 1：**

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

输入：head = [1,2,3,4,5], n = 2
    输出：[1,2,3,5]

**示例 2：**

输入：head = [1], n = 1
    输出：[]

**示例 3：**

输入：head = [1,2], n = 1
    输出：[1]

**提示：**

*  链表中结点的数目为 `sz`
 *  `1 <= sz <= 30`
 *  `0 <= Node.val <= 100`
 *  `1 <= n <= sz`

**题解**

class Solution { 
        public ListNode removeNthFromEnd(ListNode head, int n) { 
            ListNode firstNode = new ListNode();
            firstNode.next = head;
    
            ListNode p = firstNode , q = firstNode;
            int step = 0;
    
            while(q != null){ 
                if(step >= n + 1){ 
                    p = p.next;
                }
                step ++;
                q = q.next;
            }
    
            p.next = p.next.next;
            return firstNode.next;
        }
    
        
        
    }

#### [61. 旋转链表][61.] ####

难度中等412收藏分享切换为英文接收动态反馈

给定一个链表，旋转链表，将链表每个节点向右移动 *k* 个位置，其中 *k* 是非负数。

**示例 1:**

输入: 1->2->3->4->5->NULL, k = 2
    输出: 4->5->1->2->3->NULL
    解释:
    向右旋转 1 步: 5->1->2->3->4->NULL
    向右旋转 2 步: 4->5->1->2->3->NULL

**示例 2:**

输入: 0->1->2->NULL, k = 4
    输出: 2->0->1->NULL
    解释:
    向右旋转 1 步: 2->0->1->NULL
    向右旋转 2 步: 1->2->0->NULL
    向右旋转 3 步: 0->1->2->NULL
    向右旋转 4 步: 2->0->1->NULL

**题解**

class Solution { 
        public ListNode rotateRight(ListNode head, int k) { 
            int sum = 0;
            ListNode node = head;
            while(node != null){ 
                sum ++;
                node = node.next;
            }
    
            if(sum == 0){ 
                return null;
            }
            k = k % sum;
            
            ListNode p = head , q = head;
            int step = 0;
    
            while(q.next != null){ 
                if(step >= k){ 
                    p = p.next;
                }
                step ++;
                q = q.next;
            }
    
            q.next = head;
            head = p.next;
            p.next = null;
            return head;
        }
    
    
    }

#### [143. 重排链表][143.] ####

难度中等512收藏分享切换为英文接收动态反馈

给定一个单链表 *L*：*L*0→*L*1→…→*L\*\*n*\-1→*L*n ，  
将其重新排列后变为： *L*0→*L\*\*n*→*L*1→*L\*\*n*\-1→*L*2→*L\*\*n*\-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

**示例 1:**

给定链表 1->2->3->4, 重新排列为 1->4->2->3.

**示例 2:**

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

**题解**

*  正规解法：找到中间位置（快慢指针，快的走两步，慢的走一步）-> 对后半段反转 -> 归并

回溯解法

class Solution {
        public void reorderList(ListNode head) {
            int sum = 0;
            ListNode node = head;
            while(node != null){
                node = node.next;
                sum ++;
            }
            
            if(sum != 0){
                func(head , 1 , sum);
            }
        }
    
        ListNode func(ListNode head , int level , int sum){
            int midSum = (sum % 2 == 0) ? sum / 2 : sum / 2 + 1;
            if(level == midSum){
                if(sum % 2 != 0){
                    ListNode res = head.next;
                    head.next = null;
                    return res;
                }
    
                ListNode res = head.next.next;
                head.next.next = null;
                return res;
            }
    
            ListNode next = func(head.next , level + 1 , sum);
            if(next == null){
                return null;
            }
            ListNode res = next.next;
    
            next.next = head.next;
            head.next = next;
    
            return res; 
        }
    }

#### [234. 回文链表][234.] ####

难度简单840收藏分享切换为英文接收动态反馈

请判断一个链表是否为回文链表。

**示例 1:**

输入: 1->2
    输出: false

**示例 2:**

输入: 1->2->2->1
    输出: true

**题解**

*  正规解法：双指针找到中间，分成两个链表，然后比较

回溯

class Solution { 
        boolean isTrue = true;
        public boolean isPalindrome(ListNode head) { 
            ListNode node = head;
            int sum = 0;
            while(node != null){ 
                node = node.next;
                sum ++;
            }
    
            func(head , 1 ,sum);
            return isTrue;
        }
    
        ListNode func(ListNode head , int level , int sum){ 
            int midLevel = sum / 2 + 1;
            if(level == midLevel){ 
                if(sum % 2 == 0){ 
                    return head;
                }
                return head.next;
            }
    
            ListNode node = func(head.next , level + 1, sum);
            if(node.val != head.val){ 
                isTrue = false;
            }
    
            return node.next;
        }
    }

[19. _ N]: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70]: /images/20221024/43e78b083bb5419892a1847bf9306fc3.png
[61.]: https://leetcode-cn.com/problems/rotate-list/
[143.]: https://leetcode-cn.com/problems/reorder-list/
[234.]: https://leetcode-cn.com/problems/palindrome-linked-list/