「链表」专题 6:链表与双指针


「链表」专题 6:链表与双指针

例题:「力扣」第 19 题:删除链表的倒数第 N 个结点

传送门:英文网址:19. Remove Nth Node From End of List ,中文网址:19. 删除链表的倒数第N个节点

给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。

示例:

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后,链表变为 1->2->3->5.

说明:

给定的 n 保证是有效的。

进阶:

你能尝试使用一趟扫描实现吗?

思路:使用快慢指针。其实只要掌握了如何找到距离末尾 $n$ 个元素的位置,就很容易了。还要注意的就是边界值的选取,其实往往我们认为的值与正确值无非就是 $+1$ 或者 $-1$ ,为了避免粗心出错,我们可以拿一个具体的例子。另外,涉及链表头结点的操作,一般都会引入虚拟结点,以减少讨论的可能,这是一个常见的技巧。

Python 代码:

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution(object):
    def findKthToTail(self, pListHead, k):
        """
        :type pListHead: ListNode
        :type k: int
        :rtype: ListNode
        """
        if pListHead is None:
            return None
        fast = pListHead
        # 要注意的临界点1:
        for _ in range(k - 1):
            fast = fast.next
            if fast is None:
                return None
        slow = pListHead
        # 要注意的临界点2:
        while fast.next:
            slow = slow.next
            fast = fast.next
        return slow

练习1:「力扣」第 61 题:旋转链表

传送门:英文网址:61. Rotate List ,中文网址:61. 旋转链表

给定一个链表,旋转链表,将链表每个结点向右移动 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

思路:问题本身不难,但是要处理一些细节。

1、一定要先求出链表的总长度;

2、求得总长度的时候,顺便标记好末尾结点,并且把末尾结点的 next 指针指到头结点去,形成环,否则容易出现空指针异常;

3、到底多少 pre 指针还要走多少步,举 1 到 2 个具体的例子带进去就知道了。

Python 代码:

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if head is None or k <= 0:
            return head

        # 先看链表有多少元素
        node = head
        # 先数这个链表的长度
        counter = 1
        while node.next:
            node = node.next
            counter += 1

        node.next = head
        k = k % counter
        node = head
        # counter - k - 1 可以取一些极端的例子找到规律
        for _ in range(counter - k - 1):
            node = node.next
        new_head = node.next
        node.next = None
        return new_head

练习2:「力扣」第 143 题:重排链表

传送门:143. 重排链表

给定一个单链表 LL0→L1→…→L**n-1→Ln ,
将其重新排列后变为: L0→LnL1→Ln-1→L2→L**n-2→…

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

示例 1:

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

示例 2:

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

Java 代码:

/**
 * @author liwei
 * @date 18/7/5 上午9:36
 */
public class Solution2 {

    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode anotherHead = slow.next;
        // 步骤1:从中间截断链表
        slow.next = null;
        // 步骤2:反转链表的后半截
        ListNode reverseList = reverseList(anotherHead);
        // 步骤3:合并两个链表
        int k = 0;
        mergeTwoList(head, reverseList, k);
    }

    private ListNode mergeTwoList(ListNode head1, ListNode head2, int k) {
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }
        // k % 2 == 0
        if ((k & 1) == 0) {
            head1.next = mergeTwoList(head1.next, head2, ++k);
            return head1;
        } else {
            head2.next = mergeTwoList(head1, head2.next, ++k);
            return head2;
        }
    }

    private ListNode reverseList(ListNode head) {
        ListNode preNode = null;
        ListNode curNode = head;
        while (curNode != null) {
            ListNode nextNode = curNode.next;
            curNode.next = preNode;
            preNode = curNode;
            curNode = nextNode;
        }
        return preNode;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        Solution2 solution2 = new Solution2();
        ListNode head = new ListNode(nums);
        solution2.reorderList(head);
        System.out.println(head);
    }
}

练习3:「力扣」第 234 题:回文链表

传送门:234. 回文链表

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

示例 1:

输入: 1->2
输出: false

示例 2:

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

进阶:
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?

求解关键:找到链表中间位置的结点,做一些相关的处理。特别要注意的是,不管哪种方法,都要对一些细节问题仔细考虑,可以举出具体的例子,画图帮助编码实现。

思路1:从中间位置开始反转链表,逐个比较。

Java 代码:


class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }

    public ListNode(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("arr can not be empty");
        }
        this.val = nums[0];
        ListNode curr = this;
        for (int i = 1; i < nums.length; i++) {
            curr.next = new ListNode(nums[i]);
            curr = curr.next;
        }
    }

    @Override
    public String toString() {
        StringBuilder s = new StringBuilder();
        ListNode cur = this;
        while (cur != null) {
            s.append(cur.val + " -> ");
            cur = cur.next;
        }
        s.append("NULL");
        return s.toString();
    }
}


/**
 * https://leetcode-cn.com/problems/palindrome-linked-list/description/
 *
 * @author liwei
 */
public class Solution {

    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // slow 的下一个就是新链表,反转它
        ListNode cur = slow.next;
        slow.next = null;
        ListNode pre = null;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        // 此时 pre 成为新链表开头
        while (head != null && pre != null) {
            if (head.val != pre.val) {
                return false;
            }
            head = head.next;
            pre = pre.next;
        }
        return true;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 0, 2, 1};
        Solution solution = new Solution();
        ListNode head = new ListNode(nums);
        boolean palindrome = solution.isPalindrome(head);
        System.out.println(palindrome);
    }
}

思路2:在寻找链表中间结点的过程中,慢结点向前遍历的时候,把遍历到的值放入一个栈中。

Java 代码:

import java.util.Stack;

/**
 * @author liwei
 */
public class Solution2 {
    // 分清楚奇数和偶数结点两种情况,不反转链表,借助栈完成回文链表的判断
    //      slow
    // 1,2,3,4,5

    //   slow
    // 1,2,3,4

    /**
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }

        Stack<Integer> stack = new Stack<>();
        ListNode fast = head;
        ListNode slow = head;
        stack.add(slow.val);

        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            stack.add(slow.val);
        }
        if (fast.next == null) {
            // 链表有奇数个结点
            stack.pop();
        }
        slow = slow.next;
        while (slow != null) {
            if (stack.pop() != slow.val) {
                return false;
            }
            slow = slow.next;
        }
        return true;
    }

    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
        int[] nums = {1, 2, 3, 2, 1};
        ListNode head = new ListNode(nums);
        boolean palindrome = solution2.isPalindrome(head);
        System.out.println(palindrome);
    }
}

(本节完)


文章作者: liweiwei1419
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 liweiwei1419 !
评论
 上一篇
「力扣」第 2 题:两个数相加(中等) 「力扣」第 2 题:两个数相加(中等)
「力扣」第 2 题:两个数相加(中等)中文链接:2. 两数相加 ; 英文链接:2. Add Two Numbers 。 给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存
下一篇 
「链表」专题 5:不仅仅是穿针引线 「链表」专题 5:不仅仅是穿针引线
「链表」专题 5:不仅仅是穿针引线例:「力扣」第 237 题:删除链表中的结点传送门:英文网址:237. Delete Node in a Linked List ,中文网址:237. 删除链表中的节点 。 请编写一个函数,使其可以删除某
  目录