第一题:反转链表 II

LeetCode 92:

描述:

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

解题思路:

1.引用一个傀儡节点,当作反转链表后的新头,这样可以免去分类讨论的情况

2.引用一个prev指向傀儡节点,让傀儡节点和链表连接起来,当作头节点.

3.让prev走left-1步,指向的就是left位置的前一个节点,让引用一个leftNode指向left位置的节点

4.让引用一个rightNode指向right位置的节点,引用一个cur指向rightNode的下一个节点

5.反转从left位置到right位置的节点.

6.链接节点.

画图解析:

代码实现:

/**
 * 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 ListNode reverseBetween(ListNode head, int left, int right) {
        //引用一个傀儡节点当作新头,可以免去分类讨论
        ListNode newHead = new ListNode(-1);
        ListNode prev = newHead;
        prev.next = head;
        //让prev指向left所在节点之前
        while(left-1 != 0){
            prev = prev.next;
            left--;
        }
        //引用一个leftNode指向left位置
        ListNode leftNode = prev.next;
        ListNode rightNode = head;
        //让rightNode指向right位置
        while(right-1 != 0){
            rightNode = rightNode.next;
            right--;
        }
        //引用一个cur指向rightNode的下一个节点
        ListNode cur = rightNode.next;
        //让不反转的节点分离开
        prev.next=null;
        rightNode.next=null;
        //引用一个ret指向leftNode的位置
        ListNode ret = leftNode;
        ListNode tmp = leftNode.next;
        //反转链表
        while(tmp != null){
            ListNode tmpNext = tmp.next;
            tmp.next = ret;
            ret = tmp;
            tmp = tmpNext;
        }
        //连接链表,让反转后的尾节点和分离开的后半部分连接
        leftNode.next = cur;
        //让反转后的头部和prev连接
        prev.next = rightNode;
        return newHead.next;
    }
}

第二题:合并两个链表

LeetCode 1669:

描述:

给你两个链表?list1 和?list2?，它们包含的元素分别为?n 个和?m 个。

请你将?list1?中下标从 a 到 b 的全部节点都删除，并将list2?接在被删除节点的位置。

下图中蓝色边和节点展示了操作后的结果：

解题思路:

1.list1.length>=3不用考虑为空链表

2.a>=1不用考虑删除了list1的头节点.

3.引用一个left指向a-1的位置,引用一个right指向b的位置

4.让left的next域指向list2的头节点,让list2的尾节点的next域指向right.next(如果right为尾节点,list2的尾节点的next域还是null不影响)

画图解析:

代码实现:

/**
 * 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 ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        ListNode left = list1;
        ListNode right = list1;
        while(a-1 != 0){
            left = left.next;
            a--;
        }
        while(b != 0){
            right = right.next;
            b--;
        }
        ListNode last = list2;
        while(last.next != null){
            last=last.next;
        }
        left.next = list2;
        last.next = right.next;
        return list1;
    }
}

第三题:二进制链表转整数

LeetCode 1290:

描述:

给你一个单链表的引用结点?head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。

请你返回该链表所表示数字的十进制值。

解题思路:

1.转化为2进制,相当于十进制的链表转换成十进制数同理，用（sum * 10 + head.val）就可以恢复成十进制数

2.引用一个cur指向head,让cur代替head走,遍历完即可

画图解析:

代码实现:

class Solution {
    public int getDecimalValue(ListNode head) {
        ListNode cur = head;
        int sum = 0;
        while (cur!= null) {
            sum = sum * 2 + cur.val;
            cur = cur.next;
        }
        return sum;
    }
}