leetcode系列2 AddTwoNumbers

向右看齐 2022-05-21 07:22 195阅读 0赞

第二题：

You are given two linked lists representing two non-negative numbers. 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.

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

第二题就是两个链表来模仿多位整数型加法运算；

所以首先可以考虑创建单链表；

先创建节点类Node:类里面一个存储数据，一个是指向下一个节点的指针。

/**
     * 节点类
     */
    public class Node {
        protected Node next;
        private Integer data;
    
        public Node() {
        }
    
        public Node(Integer data) {
            this.data = data;
        }
    
        public Node getNext() {
            return next;
        }
    
        public void setNext(Node next) {
            this.next = next;
        }
    
        public Integer getData() {
            return data;
        }
    
        public void setData(Integer data) {
            this.data = data;
        }
    }

然后创建依据这个节点类，所构成的单链表类ListNode；里面包含创建，增加节点，删除节点，查找节点，在指定位置插入节点，打印节点值，输出链表长度这些函数。

public class ListNode {
        public Node first;
    
        //头结点
    
        public ListNode() {
            this.first = null;//初始创建 头部节点指向空
        }
    
        //增加一个节点
        public void addNode(Node node)
        {
            if(this.first ==null)
            {
                this.first = node;
                first.next = null;
            }
            else
            {
                Node tempNode = this.first;
    
                while (tempNode.getNext()!=null)
                {
                    tempNode = tempNode.getNext();
                }
    
                tempNode.setNext(node);
                node.setNext(null);
            }
        }
    
        //获取链表的长度
        public int length()
        {
            int lenght = 0;
            Node tempNode = first;
            if(tempNode == null )
            {
                return 0;
            }
    
            while (tempNode!=null)
            {
                lenght++;
                tempNode=tempNode.getNext();
            }
            return lenght;
        }
    
        //删除指定位置节点
        public void delete(int index)
        {
            if(first==null)
            {
                System.out.println("链表为空链表,无法执行删除操作");
                return;
            }
    
            if(index>length())
            {
                System.out.println("长度位置超过链表长度！");
                return;
            }
            else
            {
                Node tempNode = first;
                for(int i=1;i<length();i++)
                {
                    if(i==index)
                    {
                        Node stackNode = tempNode.getNext();
                        tempNode.setNext(stackNode.getNext());
                        return;
                    }
                    else{
                        tempNode = tempNode.getNext();
                    }
                }
            }
        }
    
    
    
        //增加指定位置的节点
        public void addNodeByIndex(int index,Node node)
        {
            if(index>length())
            {
                try {
                    throw new Exception("位置坐标输入错误，超过链表长度");
                }
                catch (Exception e)
                {
                    e.printStackTrace();
                    System.out.println("捕获位置坐标异常");
                }
            }
            else if(index == 1)
            {
                Node backNode = first;
                first = node;
                node.setNext(backNode);
            }
            else
            {
                Node frontNode = getNodeByIndex(index-1);
                Node backNode = frontNode.getNext();
                frontNode.setNext(node);
                node.setNext(backNode);
            }
        }
    
        //显示节点的信息
    
        //查找指定位置的节点
        public Node getNodeByIndex(int index)
        {
            if(index>length())
            {
                try {
                    throw new Exception("指定位置超过链表长度");
                }
                catch (Exception e)
                {
                    e.printStackTrace();
                    System.out.println("捕获数据长度异常");
                }
                return null;
            } else
            {
                Node tempNode = first;
                for(int i = 1;i<=length();i++)
                {
                    if(i<index) {
                        tempNode = tempNode.getNext();
                    }
                    else
                    {
                        break;
                    }
                }
                return tempNode;
            }
        }
    
        //显示链表信息
        public void showAllData()
        {
            if(length()==0)
            {
                System.out.println("链表中没有值！");
            }
            else
            {
                String dataInfo = "";
                int le = length();
                for(int i=1;i<=le;i++) {
                    if (i == 1) {
                        dataInfo = this.getNodeByIndex(i).getData().toString();
                    } else
                    {
                        dataInfo = dataInfo + "-->" + this.getNodeByIndex(i).getData();
                    }
                }
                System.out.println(dataInfo);
            }
        }
    }

然后就是正式开始做这个题目了。

加法里面主要需要注意的是考虑到进位，所以可以单独设置一个进位福offset，用它的值来提示对应位置是否应该加1.

这样的话，算两个链表加法，只需要把相同位置的数相加然后对10求余就可以了。

我这边考虑了，两个数字可能长度不一致的地方，那么循环的时候就需要依据短位置进行循环。

对应的函数运算就是：

public ListNode addList(ListNode listNodeOne, ListNode listNodeTwo)
        {
            int lengthOne = listNodeOne.length();
            int lenghtTwo = listNodeTwo.length();
            int shortLenght = 0;
            int longLength = 0;
            ListNode longList = new ListNode();
            if(lengthOne<lenghtTwo)
            {
                shortLenght = lengthOne;
                longLength = lenghtTwo;
                longList = listNodeTwo;
            }
            else
            {
                shortLenght = lenghtTwo;
                longLength = lengthOne;
                longList = listNodeOne;
            }
            int offset = 0;
    
            ListNode resultNode = new ListNode();
    
            for(int i=1;i<=longLength;i++)
            {
                if(i<=shortLenght) {
                    Node nodeOne = listNodeOne.getNodeByIndex(i);
                    Node nodeTwo = listNodeTwo.getNodeByIndex(i);
    
                    int value = nodeOne.getData() + nodeTwo.getData();
                    if (offset == 1) {
                        value++;
                        offset = 0;
                    }
                    if (value >= 10) {
                        offset = 1;
                    }
                    Node resultNodeData = new Node();
                    resultNodeData.setData(value % 10);
                    resultNode.addNode(resultNodeData);
                }
                else
                {
                    Node nodeTemp = longList.getNodeByIndex(i);
                    int values = nodeTemp.getData();
                    if(offset == 1)
                    {
                        values++;
                        offset = 0;
                    }
                    Node resultNodeData = new Node(values);
                    resultNode.addNode(resultNodeData);
                }
            }
            return  resultNode;
        }

具体的代码参见github：https://github.com/harrypitter/leetCode1-10.git