Day 10

剑指offer 22.链表中倒数第k个节点

题目描述

解答

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        int len=0;
        ListNode cur=head;
        while(cur !=null){
            len++;
            cur=cur.next;
        }
        
        ListNode newcur=head;
        for(int i=0;i<len-k;i++){
            newcur=newcur.next;
        }
        return newcur;
    }
}

剑指offer 24.反转链表

题目描述

解答

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null){
            return head;
        }else{
            ListNode cur=head;
            ListNode pre=null;
            while(cur!=null){
                //先保存下一个结点
                ListNode tempt=cur.next;
                cur.next=pre;
                pre=cur;
                cur=tempt;
            }
            return pre;
        }
    }
}

剑指offer 25.合并两个排序的链表

题目描述

解答

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(-1), cur = dummyHead;
        // while 跳出：l1或者l2遍历到了末尾
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                cur.next = l1;
                cur = cur.next;
                l1 = l1.next;
            } else {
                cur.next = l2;
                cur = cur.next;
                l2 = l2.next;
            }
        }
        //如果先是l2先遍历完，l1还没遍历完
        if (l1 != null) {
           cur.next = l1;
        }
        //如果先是l1先遍历完，l2还没遍历完
        if (l2 != null) {
           cur.next = l2;
        }

        return dummyHead.next;
    }
}