链表反转问题解析

一.指定区间反转

1.头插法

LeetCode92 :给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right。请你反转从位置 left 到位置 right 的链表节点,返回反转后的链表。

image-20230916205100367

反转的整体思想是,在需要反转的区间里,每遍历到一个节点,让这个新节点来到反转部分的起始位置。下面的图展示了整个流程。

image (11)

也就是说,翻转链表,总结步骤就是:

1.防止特殊情况,先建立虚拟头结点,之后走到left节点前一个节点

2.之后需要将right-left个链表进行翻转,也就是将cur.next这个节点放在cur节点之前

(1)得到cur节点(left>next),以及next节点(cur.next)

(2)将cur.next指向next.next

(3)将next的值放在cur前,next.next= pre.next;

需要注意的是这里不能写成next.next= cur,因为原理是cur始终是一个值,随着链表的翻转会不断的向后移动

(4)pre.next= next;

完整代码:

ListNode dummyNode = new ListNode(-1);
    dummyNode.next = head;
    ListNode pre = dummyNode;
    for (int i = 0; i < left - 1; i++) {
        pre = pre.next;
    }
    ListNode cur = pre.next;
    ListNode next;
    for (int i = 0; i < right - left; i++) {
        next = cur.next;
        cur.next = next.next;
        next.next = pre.next;
        pre.next = next;
    }
    return dummyNode.next;

2.穿针引线法

我们可以这么做:先确定好需要反转的部分,也就是下图的 left 到 right 之间,然后再将三段链表拼接起来。这种方式类似裁缝一样,找准位置减下来,再缝回去。这样问题就变成了如何标记下图四个位置,以及如何反转left到right之间的链表。

image (12)

第 1 步:先将待反转的区域反转;
第 2 步:把 pre 的 next 指针指向反转以后的链表头节点,把反转以后的链表的尾节点的 next 指针指向 succ。

步骤:

1.建立头结点(减少头结点特殊情况的考虑)

2.找到left节点的前一个节点,和right节点.

3.切割节点(将right.next设置为null),之后进行翻转

4.翻转后进行拼接,但是需要注意翻转后子链表的头结点是之前的尾节点

完整代码

ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        ListNode tem = pre.next;
        for (int i = 0; i < right - left ; i++) {
            tem = tem.next;
        }
        ListNode suc = tem.next;
        tem.next = null;

        ListNode pre1 = null;
        ListNode cur = pre.next;
        ListNode head1 =cur;

        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre1;
            pre1 = cur;
            cur = next;
        }
        head1.next = suc;
        pre.next = tem;

二.两两交换链表中的节点

这是一道非常重要的问题,读者务必理解清楚。

LeetCode24.给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。

如果原始顺序是 dummy -> node1 -> node2,交换后面两个节点关系要变成 dummy -> node2 -> node1,事实上我们只要多执行一次next就可以拿到后面的元素,也就是类似node2 = temp.next.next这样的操作。

 public static  ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(-1);
         ListNode tem = dummyHead;
         dummyHead.next = head;
         while (tem.next!=null&&tem.next.next!=null){
             ListNode cur = tem.next;
             ListNode next = cur.next;
             //交换位置
             cur.next = next.next;
             next.next = tem.next;
             tem.next = next;
             tem = cur;
         }
      return dummyHead.next;
    }

本题的重点:

除了与上题交换思路外;还有一些注意点

循环条件:首先cur随着循环一次后移一位,我们每两个交换位置以后需要更新tem的值,因此将tem= cur;

此时cur.next就是新的两个我们需要交换位置的两个元素,因此

当节点数量有偶数个时:到最后一个节点,cur此时一定在最后,tem.next!=null停止

当节点数量有奇数个时:我们需要判断tem.next.next是否为null,为null停止

三.单链表加1

LeetCode369.用一个非空单链表来表示一个非负整数,然后将这个整数加一。你可以假设这个整数除了 0 本身,没有任何前导的 0。这个整数的各个数位按照 高位在链表头部、低位在链表尾部 的顺序排列。

示例:

输入: [1,2,3]   

输出: [1,2,4]

本题可以通过遍历得到所有数字最后建立新的链表进行,这里使用栈来做,本题的重点在于,加减操作一定是从最后一位开始,也就是来吧最后一位开始,进位是本题的关键

思路:首先全部将数字压入栈,之后

1.得到最后一位数字,判断是否需要进位,定义一个cheery,当sum(当前位数的数字),大于等于10的时候,需要进位,当一开始就不需要进位的情况,循环内会设置为0

2.循环结束 的条件有两种,当栈中元素全部弹出的时候,以及,不需要进位运算结束后

3.最后,利用虚拟节点的指向(类似反转链表的思路)进行新链表的创建

 public static ListNode plusOne(ListNode head) {
        Stack<Integer> st = new Stack();
        while(head!=null){
            st.push(head.val);
            head= head.next;
        }
        ListNode dummy = new ListNode(-1);
        int add=1;
        int cheery =0;
        while (!st.isEmpty()||cheery>0){
            int dig = st.isEmpty()?0:st.pop();
            int sum = dig+add+cheery;
              cheery = sum>=10 ? 1 :0;
            sum = sum>=10?sum-10:sum;

            ListNode cur = new ListNode(sum);
            cur.next = dummy.next;
            dummy.next =cur;
            add = 0;

        }
        return dummy.next;
    }

四.链表的加法

思路是先将两个链表的元素分别压栈,然后再一起出栈,将两个结果分别计算。之后对计算结果取模,模数保存到新的链表中,进位保存到下一轮。完成之后再进行一次反转就行了。

我们知道在链表插入有头插法和尾插法两种。头插法就是每次都将新的结点插入到head之前。而尾插法就是将新结点都插入到链表的表尾。两者的区别是尾插法的顺序与原始链表是一致的,而头插法与原始链表是逆序的,所以上面最后一步如果不想进行反转,可以将新结点以头插法。

public static ListNode addInListByStack(ListNode head1, ListNode head2) {
    Stack<ListNode> st1 = new Stack<ListNode>();
    Stack<ListNode> st2 = new Stack<ListNode>();
    while (head1 != null) {
        st1.push(head1);
        head1 = head1.next;
    }
    while (head2 != null) {
        st2.push(head2);
        head2 = head2.next;
    }
    ListNode newHead = new ListNode(-1);
    int carry = 0;
    //这里设置carry!=0,是因为当st1,st2都遍历完时,如果carry=0,就不需要进入循环了
    while (!st1.empty() || !st2.empty() || carry != 0) {
        ListNode a = new ListNode(0);
        ListNode b = new ListNode(0);
        if (!st1.empty()) {
            a = st1.pop();
        }
        if (!st2.empty()) {
            b = st2.pop();
        }
        //每次的和应该是对应位相加再加上进位
        int get_sum = a.val + b.val + carry;
        //对累加的结果取余
        int ans = get_sum % 10;
        //如果大于0,就进位
        carry = get_sum / 10;
        ListNode cur = new ListNode(ans);
        cur.next = newHead.next;
        //每次把最新得到的节点更新到neHead.next中
        newHead.next = cur;
    }
    return newHead.next;
}

五.再论链表的回文序列问题(快慢指针和翻转部分链表法)

本题的很重要的一点细节:需要判断链表究竟是单数节点还是双数节点:如果是单数节点需要将slow的指针继续后移一位

传真引线法和直接操作法对链表的部分进行翻转思路相同:

1.当节点数量为双数的时候,不需要考虑,单数的时候翻转中间数以前的节点

2.slow指针指代的是翻转链表的next节点

3.反转后只需要将slow开始进行遍历,以及前一半链表进行比较

public boolean isPalindrome(ListNode head) {
    if(head == null || head.next == null) {
        return true;
    }
    ListNode slow = head, fast = head;
    ListNode pre = head, prepre = null;
    while(fast != null && fast.next != null) {
        pre = slow;
        slow = slow.next;
        fast = fast.next.next;
        //将前半部分链表反转
        pre.next = prepre;
        prepre = pre;
    }
    if(fast != null) {
        slow = slow.next;
    }
    while(pre != null && slow != null) {
        if(pre.val != slow.val) {
            return false;
        }
        pre = pre.next;
        slow = slow.next;
    }
    return true;
}