> 文档中心 > 十大链表金典笔试题

十大链表金典笔试题

目录

一,Leedcode面试题0205链表求和

二,Leedcode19删除链表的倒数第N个结点

三,Leedcode21合并两个有序链表

四,Leedcode82删除排序链表中的重复元素

五,Leedcode92反转链表

六,Leedcode141环形链表

七,Leedcode160相交链表

八,Leedcode234回文链表

九,Leetcode26原地删除数组中的重复项

十,面试题0204分割链表

十一,Leetcode206反转链表


一,Leedcode面试题0205链表求和

  //方法2:递归    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) { //递归终止条件 if (l2 == null){     return l1; } if (l1 == null){     return l2; } ListNode h1 = l1; ListNode h2 = l2; //我只知道当前两个链表d额头节点的和,剩下的我不知道,交给add方法 //如果有节点为空,并且temp== 0,直接返回还有节点的链表 int temp = (h1.val + h2.val ) > 9 ? 1 : 0; if (temp == 0){     h1.val = (h1.val + h2.val ); }else {//temp = 1;     h1.val = ((h1.val + h2.val) % 10);     h1.next = addIsOverTen(h1.next,temp); } h1.next = addTwoNumbers(h1.next,h2.next); return h1;    }    //方法1:开辟新空间    public static ListNode addTwoNumbers1(ListNode l1, ListNode l2) { //方法1:创建一个新链表 ListNode dummy = new ListNode(); ListNode dummyHead = dummy; if (l1 == null){     return l2; } if (l2 == null){     return l1; } ListNode h1 = l1; ListNode h2 = l2; int temp = 0; while (h1 != null && h2 != null){     int sum = h1.val + h2.val + temp;     if (sum > 9){  temp = 1;     }else {  temp = 0;     }     dummy.next = new ListNode(sum % 10);     h1 = h1.next;     h2 = h2.next;     dummy = dummy.next; } //如果有节点为空,并且temp== 0,直接返回还有节点的链表 if (temp == 0){     dummy.next = h1 == null ? h2 : h1; }else {//temp = 1;     //判断那个节点为空     if (h1 == null && h2 == null){  dummy.next = new ListNode(1);     }else if (h1 == null){  dummy.next = addIsOverTen(h2,temp);     }else {  dummy.next = addIsOverTen(h1,temp);     } } return dummyHead.next;    }    public static ListNode addIsOverTen(ListNode head,int temp){ if (head == null){     return new ListNode(temp); } ListNode cur = head; if ((cur.val + temp) > 9){     cur.val = 0;     temp = 1;     if (cur.next == null){  cur.next = new ListNode(1);     }else {  addIsOverTen(cur.next,temp);     } }else {     cur.val += 1; } return head;    }

二,Leedcode19删除链表的倒数第N个结点

public ListNode removeNthFromEnd(ListNode head, int n) { int len = 1; ListNode node = head; int count = 1; while(node.next != null){     len++;     node = node.next; } node = head; if(len == n){     head = head.next;     return head; } while(count < len-n){     node = node.next;     count++; } node.next = node.next.next; return head;    }

三,Leedcode21合并两个有序链表

 //方法1    public ListNode mergeTwoLists1(ListNode list1, ListNode list2) { //虚拟头节点 ListNode head = new ListNode(); ListNode cur = head; while (list1 != null && list2 != null){     if (list1.val <= list2.val){  cur.next = list1;  cur = list1;  list1 = list1.next;     }else {  cur.next = list2;  cur = list2;  list2 = list2.next;     } } if (list1 == null){     cur.next = list2; } if (list2 == null){     cur.next = list1; } return head.next;    }    //方法2:递归    /**     * 传入两个链表list1和list2就能拼接成一个有序的单链表,返回头节点     * @param list1     * @param list2     * @return     */    public ListNode mergeTwoLists(ListNode list1, ListNode list2) { //递归结束条件 if (list1 == null){     return list2; } if (list2 == null){     return list1; } if (list1.val <= list2.val){     list1.next = mergeTwoLists(list1.next,list2);     return list1; }else {     list2.next = mergeTwoLists(list1,list2.next);     return list2; }    }

四,Leedcode82删除排序链表中的重复元素

 //三指针法    public static ListNode deleteDuplicates1(ListNode head) { //创建一个虚拟节点,防止头节点就是重复的节点,而导致头节点无法删除 ListNode dummyHead = new ListNode(); //创建一个prev节点用来遍历虚拟节点绑定的链表 ListNode prev = dummyHead; //让虚拟节点的next指向链表的头节点 dummyHead.next = head; //创建一个新的节点,用来指向虚拟节点的下一个节点 ListNode cur = prev.next; //如果cur不为空,说明链表至少存在一个节点 while (cur != null){     //创建一个新的节点next,初识默认指向cur的next,next的作用是来用来判断cur和next是否为重复节点     ListNode next = cur.next;     //next=null,说明此时已经将整个链表遍历结束(链表只有一个元素),此时返回dummyHead.next;     if (next == null){  return dummyHead.next;     }     //走到这里说明此时链表的遍历没有到最后     //如果cur和next节点的值相等,说明节点是重复的,此时所有需要删除节点,如果不相等,说明没有重复节点,三个指针同时向后移动,开始下一次while循环     //如果不相等,执行if语句,说明此时节点不为重复节点     if (cur.val != next.val){  //将三个节点全部后移一位,这里只写prev后移和cur的后移,是应为next在进入while循环时,定义的就是cur的下一个节点,默认就相当于后移一位  prev = prev.next;  cur = cur.next;     }else {  //如果存在重复值,next一直后移,直到找到不重复的节点,找到next与cur不重复的节点以后,将prev.next = next;直接删除prev到next之间所有重复的节点  //因为要执行next = next.next,所以在这里需要保证next不为空,否则会空指针异常  while (next != null && cur.val == next.val){      next = next.next;  }  //走到这里说明此时next节点与cur不重复,让prev.next指向next,删除所有重复的节点,让cur=next,开始下一次循环时,cur = next ,next = cur.next;继续用来判断是否存在重复节点  prev.next = next;  cur = next;     } } //走到这里说明此时已经遍历完成所有的节点,返回dummy.next; //因为dummyHead没有存储val,dummyhead.next指向head头节点,所以返回demmyHead.next; return dummyHead.next;    }    //递归解法    /**     * 方法语义:给你一个链表的头节点,你就可以删除链表中所有重复出现的所有节点     * @param head     * @return     */    //此方法不对,分析的思路不对    public static ListNode deleteDuplicates2(ListNode head) { //1.终止条件 //如果链表为空,或者链表中只有一个节点,肯定就不会存在重复节点 if (head == null || head.next == null){     return head; } //走到这里说明链表至少存在两个节点 //需要创建一个虚拟节点用来删除头节点就是重复节点的情况 ListNode dummyHead = new ListNode(); dummyHead.next = head; //将头节点以后的节点传入具有删除重复节点的方法中,会返回一个新的节点 ListNode newHead = deleteDuplicates(head.next); //判断newHead和head的是否重复 if (head.val == newHead.val){     //执行到此,说明节点head和剩余节点删除重复节点以后返回的新节点相等,说明head和newHead重复。     //此时将dummyHead.next = newHead.next就会将head和newHead重复的节点全部删掉     dummyHead.next = newHead.next; }else {     //走到这里,说明head和newHead不重复,直接拼接     head.next = newHead; } //拼接完成,返回dummyHead.next return dummyHead.next;    }    /**     * 方法语义:给你一个链表的头节点,你就可以删除链表中所有重复出现的所有节点,返回一个新节点     * @param head     * @return     */    public static ListNode deleteDuplicates(ListNode head) { //终止条件 if (head == null || head.next == null){     return head; } //说明至少存在两个节点 //判断两节点是否相等,如果不相等 if (head.val != head.next.val){     //如果不相等 ,  当前头节点直接拼接剩余节点删除重复节点的后返回的新节点头     head.next = deleteDuplicates(head.next);     return head; }else {     //两节点重复     ListNode node = head.next;     while (node != null && node.val == head.val){  node = node.next;     }     //如果重复,找到重复的节点以后,调用改方法,直接不和头节点拼接,直接返回,就会将重复的头节点一并删除掉     return deleteDuplicates(node); }    }

五,Leedcode92反转链表

ListNode successor;    public ListNode reverseBetween(ListNode head, int left, int right) { if (left == 1){     return reverseN(head,right); } head.next = reverseBetween(head.next,left-1,right-1); return head;    }    //反转前N个节点    public ListNode reverseN(ListNode head,int n) { //如果n==1,则说明就反转一个节点,就等于不反转 if (n == 1){     successor = head.next;     return head; } //n > 2 ListNode temp = head.next; ListNode newHead = reverseN(head.next,n-1); temp.next = head; head.next = successor; return newHead;    }    /**     * 给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。     * 就反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。     *     * 链表中节点数目为 n     * 1 <= n <= 500     * -500 <= Node.val <= 500     * 1 <= left <= right <= n     *     * @param head     * @param left     * @param right     * @return     */    public ListNode reverseBetween1(ListNode head, int left, int right) { //递归终止条件,如果head.next == null,直接返回 if (head.next == null){     return head; } ListNode cur = new ListNode(); cur.next = head; ListNode before = cur; //否则找到需要   反转的节点的  前驱节点before;  假如left = 2,i = 0,i for (int i = 0; i < left - 1; i++) {     before = before.next; } //找反转节点的开始节点 ListNode leftNode = before.next; //然后将before指向空,避免环状链表。 before.next = null; //找到需要反转的节点的末节点 ListNode cur1 = new ListNode(); cur1 = leftNode; for (int i = 0; i < right - left; i++) {     cur1 = cur1.next; } ListNode end = new ListNode(); //找到反转链表的尾节点 ListNode rightNode = cur1; //记录要反转链表  尾节点的下一个节点end; end = rightNode.next; //将rightNode.next 质控,避免环形链表 rightNode.next = null; //然后反转需要反转的部分链表 ListNode reverseList = reverseList(leftNode); // 然后拼接前一半 before.next = reverseList; //拼接后一半,后一半的节点的尾节点现在经过反转,leftNode成了reverseList的为节点 leftNode.next = end; //     //返回结果 return cur.next;    }    public ListNode reverseList(ListNode head) { //1递归终止条件 if (head == null || head.next == null) {     return head; } //保存第二个节点的地址 ListNode temp = head.next; //将第二节点以后反转,得到新头节点 ListNode node = reverseList(head.next); //让第二个节点的next指向head temp.next = head; //消除环 head.next = null; //2得到剩余节点逆转后的链表, return node;    }

六,Leedcode141环形链表

public boolean hasCycle1(ListNode head) { if (head == null || head.next == null){     return false; } //方法1:快慢指针 ListNode slow = head; ListNode fast = head.next; while (slow != fast){     if (fast == null || fast.next == null){  return false;     }     slow = slow.next;     fast = fast.next.next; } return true;    }    //方法1:set去重    public boolean hasCycle(ListNode head) { Set set = new HashSet(); int count = 0; while (head != null){     if (set.contains(head)){  return true;     }     set.add(head);     head = head.next; } return false;    }

七,Leedcode160相交链表

public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode l1 = headA; ListNode l2 = headB; while(l1 != l2){     l1 = l1 == null ? headB : l1.next;     l2 = l2 == null ? headA : l2.next; } return l1;    }

八,Leedcode234回文链表

//方法1:先全部反转,在全部比较    public boolean isPalindrome1(ListNode head) { ListNode node = reverseList(head); while (head != null){     if (head.val != node.val){  return false;     }     node = node.next;     head = head.next; } return true;    }    public ListNode reverseList1(ListNode head) { if (head == null || head.next == null){     return head; } //方法1.临时节点 ListNode dummyHead = new ListNode(); //链表的第一个节点已经在新链表中 while (head != null){     //开始执行新的链表     ListNode node = new ListNode(head.val);     node.next = dummyHead.next;     dummyHead.next = node;     head = head.next; } return dummyHead.next;    }    //方法2:先快慢指针,在逆转后一半链表    public static boolean isPalindrome(ListNode head) { ListNode middleNode = middleNode(head); ListNode node = reverseList(middleNode); while (node != null){     if (node.val != head.val){  return  false;     }     head = head.next;     node = node.next; } return true;    }    public static ListNode middleNode(ListNode head){ ListNode frs = head,sec = head; while (sec != null && sec.next != null){     frs = frs.next;     sec = sec.next.next; } return frs;    }    public static ListNode reverseList(ListNode head) { if (head == null || head.next == null){     return head; } ListNode node = head.next; ListNode newNode = reverseList(head.next); node.next = head; head.next = null; return newNode;    }

九,Leetcode26原地删除数组中的重复项

 public static int removeDuplicates(int[] nums) { int left = 0,right = 0; while (right < nums.length){     //如果左边等于不等于右边,左边++,右边++     if (nums[left] != nums[right]){  left++;  nums[left] = nums[right];     }     right++; } return left+1;    }    public static int removeDuplicates1(int[] nums) { //单指针 int left = 0,right = 0; for (int i = 1; i < nums.length; i++) {     //如果相邻两元素相等     if (nums[i] == nums[i-1]){  continue;     }else {  left++;  nums[left] = nums[i];     } } return left+1;    }

十,面试题0204分割链表

public ListNode partition(ListNode head, int x) { if (head == null || head.next == null){     return head; } ListNode smailHead = new ListNode(); ListNode smailTail = smailHead; ListNode bigHead = new ListNode(); ListNode bigTail = bigHead; while (head != null){     if (head.val < x){  smailTail.next = head;  smailTail = head;     }else {  bigTail.next = head;  bigTail = head;     }     head = head.next; } bigHead.next = null; smailTail.next = bigHead.next; return smailHead.next;    }

十一,Leetcode206反转链表

 //方法1:临时节点    public static ListNode reverseList2(ListNode head) { if (head == null || head.next == null){     return head; } //方法1.临时节点 ListNode prev = new ListNode(); //链表的第一个节点已经在新链表中 prev.next = null; while (head != null){     //开始执行新的链表     ListNode temp = head.next;     head.next = prev.next;     prev.next = head;     head = temp; } return prev.next;    }    //方法2:三指针    public ListNode reverseList1(ListNode head) { if (head == null || head.next == null){     return head; } ListNode prev = new ListNode(); ListNode sec = head; while (sec != null){     ListNode temp = sec.next;     sec.next = prev;     prev = sec;     sec = temp; } return prev;    }    //方法3:递归    /**     * 哥你一你个单链表,你就能将链表反转,并返回头节点     * @param head     * @return     */    public ListNode reverseList(ListNode head) { //1递归终止条件 if (head == null || head.next == null) {     return head; } //保存第二个节点的地址 ListNode temp = head.next; //将第二节点以后反转,得到新头节点 ListNode node = reverseList(head.next); //让第二个节点的next指向head temp.next = head; //消除环 head.next = null; //2得到剩余节点逆转后的链表, return node;    }