程序员面试金典:链表--链式A+B、回文链表

本文主要是介绍程序员面试金典:链表--链式A+B、回文链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.链表--链式A+B

题目描述

有两个用链表表示的整数，每个结点包含一个数位。这些数位是反向存放的，也就是个位排在链表的首部。编写函数对这两个整数求和，并用链表形式返回结果。

给定两个链表ListNode* A，ListNode* B，请返回A+B的结果(ListNode*)。

测试样例：

{1,2,3},{3,2,1}

返回：{4,4,4}

public ListNode plusAB(ListNode a, ListNode b) {ListNode head=new ListNode(-1);ListNode cur=head;int carry=0;while(a!=null||b!=null||carry!=0){int a_val=a!=null?a.val:0;int b_val=b!=null?b.val:0;int res=(a_val+b_val+carry)%10;carry=(a_val+b_val+carry)/10;cur.next=new ListNode(res);cur=cur.next;a=a!=null?a.next:null;b=b!=null?b.next:null;}return head.next;}

2.回文链表

题目描述

请编写一个函数，检查链表是否为回文。

给定一个链表ListNode* pHead，请返回一个bool，代表链表是否为回文。

测试样例：

{1,2,3,2,1}

返回：true

{1,2,3,2,3}

返回：false

解法1：用ArrayList方法

public boolean isPalindrome(ListNode pHead) {ArrayList<Integer> list=new ArrayList<Integer>();if(pHead==null)	return false;while(pHead!=null){list.add(pHead.val);pHead=pHead.next;}int len=list.size();int arr[]=new int[1+len/2];for(int i=0;i<arr.length;i++){arr[i]=list.get(i);}for(int j=0;j<arr.length-1;j++){list.remove(0);}for(int m=list.size()-1,n=0;n<arr.length&&m>=0;m--,n++){if(arr[n]!=list.get(m)){return false;}}return true;}

解法2：用栈来实现的，效果不错

import java.util.*;/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Palindrome {public boolean isPalindrome(ListNode pHead) {// write code hereStack<ListNode> stack=new Stack<>();int len=0;ListNode node=pHead;while(pHead!=null){len++;stack.push(pHead);pHead=pHead.next;}int n=len/2;while(n!=0){if(node.val!=stack.pop().val){return false;}node=node.next;n--;}return true;}
}

这篇关于程序员面试金典:链表--链式A+B、回文链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！