时间：2017年11月8日22:15:38 星期三

Add Two Numbers

Description

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0);
    ListNode p = l1, q = l2, curr = dummyHead;
    int carry = 0;
    while (p != null || q != null) {
        int x = (p != null) ? p.val : 0;
        int y = (q != null) ? q.val : 0;
        int sum = carry + x + y;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return dummyHead.next;
}

Node：

/**
 * Created by cyc20 on 2017/11/1.
 */
public class Node {
    int digit;
    Node next;
    public Node(int digit){
        this.digit=digit;
        this.next=null;
    }
    public int getDigit(){
        return digit;
    }

    public Node getNext() {
        return next;
    }

    public void setDigit(int digit) {
        this.digit = digit;
    }

    public void setNext(Node next) {
        this.next = next;
    }

}

import java.util.List;

/**
 * Created by cyc20 on 2017/11/8.
 */
public class main {
    public static void main(String []args){
        Node l1=new Node(1);
        Node l2=new Node(2);
        Node l3=new Node(3);
        l1.next=l2;
        l2.next=l3;
        l3.next=null;
        Node s1=new Node(9);
        Node s2=new Node(2);
        //Node s3=new Node(3);
        s1.next=s2;
        //s2.next=s3;
        //s3.next=null;
        Node result;
        result=addTwoNumber(l1,s1);
        while (result!=null){
            System.out.println(String.valueOf(result.getDigit()));
            result=result.next;
        }
    }
    public static Node addTwoNumber(Node p,Node q){
       Node result=new Node(0);
       Node l1=p,l2=q,cur=result;
       int carry=0;
       while (l1!=null||l2!=null){
           int x=(l1!=null)?l1.getDigit():0;
           int y=(l2!=null)?l2.getDigit():0;
           int sum=carry+x+y;
           carry=sum/10;
           result.next=new Node(sum%10);
           result=result.next;
           if (l1!=null)l1=l1.next;
           if (l2!=null)l2=l2.next;
       }
       if (carry>0){
           result.next=new Node(carry);
       }

       return cur.next;


    }
}

Remove Nth Node From End of List

Discription

Given a linked list, remove the nth node from the end of list and return its head.
For example,

Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.

Solution

Approach 1

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    int length  = 0;
    ListNode first = head;
    while (first != null) {
        length++;
        first = first.next;
    }
    length -= n;
    first = dummy;
    while (length > 0) {
        length--;
        first = first.next;
    }
    first.next = first.next.next;
    return dummy.next;
}

Approach2

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode first = dummy;
    ListNode second = dummy;
    // Advances first pointer so that the gap between first and second is n nodes apart
    for (int i = 1; i <= n + 1; i++) {
        first = first.next;
    }
    // Move first to the end, maintaining the gap
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    second.next = second.next.next;
    return dummy.next;
}