编程导航算法村第二关 | 白银挑战

指定区间的链表翻转

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

public ListNode reverseBetween(ListNode head, int left, int right) {
//        确定翻转列表的左起始节点
        ListNode domo = new ListNode(0);
        domo.next = head;
//        System.out.println(head);
        int i = 0;
        ListNode temp = domo;

        while (i < left - 1) {
            temp = temp.next;
            i++;
        }
//        System.out.println(temp.val);

        保存前一个
        ListNode preNode = temp;
        ListNode leftNode = temp.next;


        确定翻转列表的右结束节点
        i = 0;
        while (i < (right - left + 1)) {
            temp = temp.next;
            i++;
        }
//

        保存它的后一个
        ListNode rightNode = temp;

        ListNode afterNode = temp.next;

        preNode.next = null;
        rightNode.next = null;

//        翻转指定区间列表
        temp = leftNode;

        ListNode pre = null;
        ListNode cul = leftNode;
        while (cul != null) {
            ListNode next = cul.next;
            cul.next = pre;
            pre = cul;
            cul = next;
//            temp = temp.next;
        }
//        System.out.println(rightNode.next.val);
        preNode.next = rightNode;
        leftNode.next = afterNode;


        return domo.next;
    }

两两交换链表

LeetCode24 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题

 public ListNode swapPairs(ListNode head) {
//    设置虚拟头结点
        ListNode node = new ListNode(0);
        node.next = head;
        ListNode temp = node;
//        遍历到倒数第三个为止
        while (temp.next != null && temp.next.next != null) {
            ListNode n = temp.next.next;
            temp.next.next = n.next;
            n.next = temp.next;
            temp.next = n;

            temp = temp.next.next;
        }
        return node.next;
    }

实现单链表的+1

• 在此处，我们采取的思路是，现将链表进行翻转，然后给第一个节点+1，保存进位值，往后的节点与进位值相加
• 
  注意
  
  ：我们需要考虑当遍历到最后一个元素还有进位的情况即999，这种情况，我们需要新建一个节点，插入到链表末尾
• 再次翻转元素

/**
     * 实现单链表所有元素+1的操作
     */
    public static ListNode addOne(ListNode head) {

        if (head == null) {
            return null;
        }

        ListNode pre = reverse(head);

        ListNode temp = pre;

        int cut = 0; //进位
//        现将第一个元素添加了进位
        int sum = 0;
        sum = temp.val + 1;

        if (sum >= 10) {
            temp.val = sum % 10;
            cut = 1;
        } else {
            cut = 0;
            temp.val = sum;
        }
        temp = temp.next;
        while (temp != null) {
            sum = temp.val + cut;

            if (sum >= 10) {
                temp.val = sum % 10;
                cut = sum / 10;
            } else {
                temp.val = sum;
                cut = 0;
            }
//            到了最后一个，如果是最后一个还有进位，说明需要添加一位数
            if (temp.next == null) {
                if (cut == 1) {
                    ListNode listNode = new ListNode(1);
                    temp.next = listNode;
                    break;
                }
            }
            temp = temp.next;
        }

        return reverse(pre);


    }

    /**
     * 定义翻转的函数
     */
    public static ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
//
        while (cur != null) {
            ListNode temp = cur.next;

            cur.next = pre;

            pre = cur;
            cur = temp;
        }

        return pre;

    }

链表加法

• 现将两个待相加的链表翻转，然后进行相加
• 分两种情况
  • 位数相同
  • 位数不同

 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return null;
        }

//         先翻转链表
        ListNode nl1 = reverse(l1);
        ListNode nl2 = reverse(l2);

        ListNode result = new ListNode(0);
        ListNode temp = result;

        int cul = 0;
        int sum = 0;
//                现将相同的位数进行相加
        while (nl1 != null && nl2 != null) {
            sum = nl1.val + nl2.val + cul;

            if (sum >= 10) {
                cul = 1;
                sum = sum % 10;
            } else {
                cul = 0;
            }

            ListNode node = new ListNode(sum);

            temp.next = node;

            temp = temp.next;

            nl1 = nl1.next;

            nl2 = nl2.next;

//            考虑两者位数一样，同时到达末尾
            if (nl1 == null && nl2 == null) {
                if (cul != 0) {
                    node = new ListNode(cul);
                    temp.next = node;

                }
            }
        }

//
        if (nl1 != null) {
            while (nl1 != null) {
                sum = nl1.val + cul;
                if (sum >= 10) {
                    cul = sum / 10;
                    sum = sum % 10;
                } else {
                    cul = 0;
                }

                temp.next = new ListNode(sum);
                temp = temp.next;
                nl1 = nl1.next;
                if (nl1 == null && cul != 0) {
                    temp.next = new ListNode(1);
                    break;
                }
            }
        }

        if (nl2 != null) {
            while (nl2 != null) {
                sum = nl2.val + cul;
                if (sum >= 10) {
                    cul = sum / 10;
                    sum = sum % 10;
                } else {
                    cul = 0;
                }
                temp.next = new ListNode(sum);
                temp = temp.next;
                nl2 = nl2.next;
                if (nl2 == null && cul != 0) {
                    temp.next = new ListNode(1);
                    break;
                }
            }
        }

        return reverse(result.next);

    }