当前位置: 澳门新濠3559 > 编程 > 正文

面试官也常常用链表来考察面试者的基本能力,

时间:2019-10-06 23:57来源:编程
为了增长一下自己的数据结构能力,也为了面试准备,准备将剑指Offer做一下,并与各位分享,希望各位可以对代码以及思路提提建议,欢迎志同道合者,谢谢。 链表是最基本的数据结

为了增长一下自己的数据结构能力,也为了面试准备,准备将剑指Offer做一下,并与各位分享,希望各位可以对代码以及思路提提建议,欢迎志同道合者,谢谢。

链表是最基本的数据结构,面试官也常常用链表来考察面试者的基本能力,而且链表相关的操作相对而言比较简单,也适合考察写代码的能力。链表的操作也离不开指针,指针又很容易导致出错。综合多方面的原因,链表题目在面试中占据着很重要的地位。本文对链表相关的面试题做了较为全面的整理,希望能对找工作的同学有所帮助。

【声明】
欢迎转载,但请保留文章原始出处→_→
文章来源:http://www.jianshu.com/p/08d085b34b2c
联系方式:zmhg871@gmail.com

Description

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

题目:输入一个链表,反转链表后,输出新链表的表头。大三的发生的环境

链表结点声明如下:

【正文】
链表是非常基础和灵活的数据结构,在面试中出现的频率非常高。以下是我在学习《剑指offer》过程中对链表问题的总结,希望对大家复习有帮助。
(Java实现)

Example

For example,Given this linked list: 1->2->3->4->5For k = 2, you should return: 2->1->4->3->5For k = 3, you should return: 3->2->1->4->5

思路:

struct ListNode
{
int m_nKey;
ListNode * m_pNext;

【目录】

思路

  • k-group反转
  • 首先写一个单链表反转函数,指定头结点和尾节点,然后再函数中反转链表
  • 从给定链表头开始,每次读取k个长度的链表,调用反转函数,然后再继续这个过程
  • 注意考虑两个反转链表之间的连接时候的情况
  • ### 代码
/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode : val, next {} * }; */class Solution {public:    ListNode* reverseKGroup(ListNode* head, int k) {        if return head;                ListNode *res = NULL, *ptr = NULL, *cur = NULL, *pre = NULL;        while{            int count = k;            ptr = NULL;            cur = head;            //while实现每次截取k个长度的链表            while{                if(ptr == NULL)                    ptr = head;                                    cur = head;                head = head->next;                count--;                if(count == 0) break;            }                        //此时需要反转            if(count == 0 && cur && ptr){                Reverse(&ptr, &cur);            }                         //连接两个反转部分或不反转部分            if{                pre = cur;            }            else{                pre->next = ptr;                pre = cur;            }                     //记录反转链表的头节点            if res = ptr;                        //特殊情况考虑,即刚好反转到链表末尾            if(!head && count == 0) pre->next = NULL;        }                return res;    }        //反转单链表    void Reverse(ListNode **head, ListNode **tail){        ListNode *end = *tail, *cur = *head, *ptr = NULL, *tmp = NULL;               ptr = cur->next;         *tail = cur;        while(ptr != end){            tmp = ptr->next;            ptr->next = cur;            cur = ptr;            ptr = tmp;        }                if(ptr != end)            end->next = ptr;        else            end->next = cur;                   *head = end;    }};

假设链表1-2-3-4-5-6-7长度为7的链表,要反转为7-6-5-4-3-2-1

};

  1. 单链表的创建和遍历
  2. 求单链表中节点的个数
  3. 查找单链表中的倒数第k个结点
  4. 查找单链表中的中间结点
  5. 合并两个有序的单链表,合并之后的链表依然有序
  6. 反转链表
  7. 从尾到头打印单链表
  8. 删除链表结点

我们新建一个链表头,一个中间节点k, 第一步,我们将1这个节点的next赋值给中间节点k,然后我们将1这个节点设置为链表头,1的next为null,然后我们在将k这个节点保存,然后k的next设置为k,前面保存的k设置为链表头,next设置为1

题目列表:

【提示】
当我们用一个指针遍历链表不能解决问题的时候,可以尝试用两个指针来遍历链表,可以让其中一个指针遍历的速度快一些(比如一次在链表中走两步),或者让它先在链表上走几步。

代码实现

1. 求单链表中结点的个数
2. 将单链表反转
3. 查找单链表中的倒数第K个结点(k > 0)
4. 查找单链表的中间结点
5. 从尾到头打印单链表
6. 已知两个单链表pHead1 和pHead2 各自有序,把它们合并成一个链表依然有序
7. 判断一个单链表中是否有环
8. 判断两个单链表是否相交
9. 求两个单链表相交的第一个节点
10. 已知一个单链表中存在环,求进入环中的第一个节点
11. 给出一单链表头指针pHead和一节点指针pToBeDeleted,O(1)时间复杂度删除节点pToBeDeleted

  • 求链表的倒数K个节点
  • 求链表的中间节点
  • 求链表中是否有环
package com.itzmn.offer;/** * @Auther: 张梦楠 * @Date: 2018/7/30 10:24 * 简书:https://www.jianshu.com/u/d611be10d1a6 * 码云:https://gitee.com/zhangqiye * @Description: */public class Offer15 { public static void main(String[] args) { new Offer15; } private void init() { ListNode listNode = new ListNode; ListNode listNode1 = new ListNode; ListNode listNode3 = new ListNode; ListNode listNode4 = new ListNode; ListNode listNode5 = new ListNode; listNode.next = listNode1; listNode1.next = listNode3; listNode3.next = listNode4; listNode4.next = listNode5; ListNode listNode2 = ReverseList; display(listNode2); } /** * 反转链表,返回新链表的表头 * 思路: * 将每个节点分开之后,将后一个节点的next指向前一个节点 * @param head * @return * 1 2 3 */ public ListNode ReverseList(ListNode head) { //保存链表节点的前一个节点 ListNode pre = null; //保存链表节点的下一个节点 ListNode next = null; while (head != null){ next = head.next; head.next = pre; pre = head; head = next; } return pre; } public class ListNode { int val; ListNode next = null; ListNode { this.val = val; } } public void display(ListNode node){ while (node != null){ System.out.print(node.val  " "); node = node.next; } System.out.println(); }}

详细解答


希望大家可以多多指点,优化一下,QQ群:552113611

1. 求单链表中结点的个数

  1. 单链表的创建和遍历:

这是最最基本的了,应该能够迅速写出正确的代码,注意检查链表是否为空。时间复杂度为O(n)。参考代码如下:

澳门新濠3559 1

public class LinkList {

     //Linked List Node
     static class LinkNode{
         int value;                // value for this node
         LinkNode next = null;     // Pointer to next node

         LinkNode(int data){
             value = data;
         }

         LinkNode(){}
     }

     private LinkNode header = null;

     //方法:向链表中添加数据
     public void add(int value){
         if(header == null) header = new LinkNode();

         LinkNode node = new LinkNode(value);
         node.next = header.next;
         header.next  = node;
     }

    //方法:遍历链表
     public void print(){
         if(header == null) return;

         LinkNode temp = header.next;
         while(temp != null){
             System.out.println("value : "   temp.value);
             temp = temp.next;
         }
     }

     public static void main(String[] args) {       
         LinkList list = new LinkList();
         //向LinkList中添加数据
         for (int i = 0; i < 7; i  ) {
              list.add(i);
          }

         list.print();
         System.out.println(list.getSize());
      }
}
 1 // 求单链表中结点的个数  
 2 unsigned int GetListLength(ListNode * pHead)  
 3 {  
 4     if(pHead == NULL)  
 5         return 0;  
 6   
 7     unsigned int nLength = 0;  
 8     ListNode * pCurrent = pHead;  
 9     while(pCurrent != NULL)  
10     {  
11         nLength  ;  
12         pCurrent = pCurrent->m_pNext;  
13     }  
14     return nLength;  
15 }  
  1. ****求单链表中节点的个数:时间复杂度为O(n)****

澳门新濠3559 2

**

//方法:获取单链表节点的个数
 public int getSize(){
     if(header == null) return 0;

     LinkNode temp = header.next;
     int size = 0;

     while(temp != null){
         size  ;
         temp = temp.next;
     }

     return size;
 }
  1. 将单链表反转**
  1. 查找单链表中的倒数第k个结点

从头到尾遍历原链表,每遍历一个结点,将其摘下放在新链表的最前端。注意链表为空和只有一个结点的情况。时间复杂度为O(n)。参考代码如下:

题目描述:输入一个单向链表,输出该链表中倒数第k个节点,链表的倒数第1个节点为链表的尾指针。 (剑指offer,题15)

澳门新濠3559 3

3.1 普通思路:(遍历链表2次)
首先计算出链表的长度size,然后输出第(size-k)个节点就可以了。
(注意链表为空,k为0,k大于链表中节点个数时的情况)。

 1 // 反转单链表  
 2 ListNode * ReverseList(ListNode * pHead)  
 3 {  
 4         // 如果链表为空或只有一个结点,无需反转,直接返回原链表头指针  
 5     if(pHead == NULL || pHead->m_pNext == NULL)    
 6         return pHead;  
 7   
 8     ListNode * pReversedHead = NULL; // 反转后的新链表头指针,初始为NULL  
 9     ListNode * pCurrent = pHead;  
10     while(pCurrent != NULL)  
11     {  
12         ListNode * pTemp = pCurrent;  
13         pCurrent = pCurrent->m_pNext;  
14         pTemp->m_pNext = pReversedHead; // 将当前结点摘下,插入新链表的最前端  
15         pReversedHead = pTemp;  
16     }  
17     return pReversedHead;  
18 } 
public int getLastNode(int index){
     if(header == null || index == 0) return -1;

     int size = getSize();
     if(index > size) return -1;

     LinkNode temp = header.next;
     for(int i =1;i<= size-index;i  ){
         temp = temp.next;
     }
     return temp.value;
 }

澳门新濠3559 4

3.2 改进思路:(遍历链表1次)
声明两个指针:first和second,首先让first和second都指向第一个结点,然后让first结点往后挪k-1个位置,此时first和second就间隔了k-1个位置,然后整体向后移动这两个节点,直到first节点走到最后一个结点的时候,此时second节点所指向的位置就是倒数第k个节点的位置。

3. 查找单链表中的倒数第K个结点(k > 0)澳门新濠3559,**

  public int getLastNode(int k){
     if(header == null || k<= 0) return -1;

     LinkNode first = header;
     LinkNode second = header;

     //让first结点往后挪k-1个位置
     for(int i =0;i<k-1;i  ){
         if(first.next != null){
             first = first.next;
         }else{
             return -1;
         }
     }
     while(first.next != null){
         first = first.next;
         second = second.next;
     }
     return second.value;
}

最普遍的方法是,先统计单链表中结点的个数,然后再找到第(n-k)个结点。注意链表为空,k为0,k为1,k大于链表中节点个数时的情况。时间复杂度为O(n)。代码略。

  1. 查找单链表中的中间结点

这里主要讲一下另一个思路,这种思路在其他题目中也会有应用。

题目描述:求链表的中间节点,如果链表的长度为偶数,返回中间两个节点的任意一个,若为奇数,则返回中间节点。

主要思路就是使用两个指针,先让前面的指针走到正向第k个结点,这样前后两个指针的距离差是k-1,之后前后两个指针一起向前走,前面的指针走到最后一个结点时,后面指针所指结点就是倒数第k个结点。

4.1 普通思路:(遍历链表2次)
首先计算出链表的长度size,然后输出第(size/2)个节点就可以了。

参考代码如下:

     public int getMiddleNode(){
         if(header == null)
             return -1;

         //第1次遍历获取节点数
         LinkNode temp = header.next;
         int size = 0;
         while(temp != null){
             size  ;
             temp = temp.next;
         }
         if(size == 0) return -1;

        //第2次遍历查找中间节点
         temp = header.next;
         for(int i=0;i<size/2;i  ){
             temp = temp.next;
         }
         return temp.value;
     }

澳门新濠3559 5

4.2 改进思路:(遍历链表1次)
声明两个指针:first和second,同时从链表头节点开始,一个指针每次移动两步,另一个每次移动一步,当走的快的指针走到链表的末尾时,走的慢的指针正好在链表的中间。

 1 // 查找单链表中倒数第K个结点  
 2 ListNode * RGetKthNode(ListNode * pHead, unsigned int k) // 函数名前面的R代表反向  
 3 {  
 4     if(k == 0 || pHead == NULL) // 这里k的计数是从1开始的,若k为0或链表为空返回NULL  
 5         return NULL;  
 6   
 7     ListNode * pAhead = pHead;  
 8     ListNode * pBehind = pHead;  
 9     while(k > 1 && pAhead != NULL) // 前面的指针先走到正向第k个结点  
10     {  
11         pAhead = pAhead->m_pNext;  
12         k--;  
13     }  
14     if(k > 1)     // 结点个数小于k,返回NULL  
15         return NULL;  
16     while(pAhead->m_pNext != NULL)  // 前后两个指针一起向前走,直到前面的指针指向最后一个结点  
17     {  
18         pBehind = pBehind->m_pNext;  
19         pAhead = pAhead->m_pNext;  
20     }  
21     return pBehind;  // 后面的指针所指结点就是倒数第k个结点  
22 }  
     public LinkNode getMiddleNode(){
         if(header == null)
             return null;

         LinkNode first = header; //快指针
         LinkNode second = header;

         while(first!=null && first.next!=null){
             first = first.next.next;
             second = second.next;
         }
         return second;
     }

澳门新濠3559 6

  1. 合并两个有序的单链表,合并之后的链表依然有序

4. 查找单链表的中间结点

题目描述:输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按照递增排序的。 (剑指offer,题17)
例如:
链表1: 1->3->5->7
链表2: 2->4->6->8
合并之后:1->2->3->4->5->6->7->8

此题可应用于上一题类似的思想。也是设置两个指针,只不过这里是,两个指针同时向前走,前面的指针每次走两步,后面的指针每次走一步,前面的指针走到最后一个结点时,后面的指针所指结点就是中间结点,即第(n/2 1)个结点。注意链表为空,链表结点个数为1和2的情况。时间复杂度O(n)。参考代码如下:

解题思路 : 类似于归并排序
首先分析合并两个链表的过程。链表1的头结点的值小于链表2的头结点的值,因此链表1的头结点将是合并后链表的头结点。
我们继续合并两个链表中剩余的结点。在两个链表中剩下的结点依然是排序的,因此合并这两个链表的步骤和前面的步骤是一样的。我们还是比较两个头结点的值。此时链表2的头结点的值小于链表1的头结点的值,因此链表2的头结点的值将是合并剩余结点得到的链表的头结点。我们把这个结点和前面合并链表时得到的链表的尾节点链接起来。
当我们得到两个链表中值较小的头结点并把它链接到已经合并的链表之后,两个链表剩余的结点依然是排序的,因此合并的步骤和之前的步骤是一样的。这就是典型的递归的过程,我们可以定义递归函数完成这一合并过程。

澳门新濠3559 7

 //两个参数代表的是两个链表的头结点,返回合并后的头结点
 public static LinkNode Merge(LinkNode head1,LinkNode head2){
     if(head1 == null) return head2;
     if(head2 == null) return head1;

     LinkNode mergeHead = null;
     if(head1.value <= head2.value){
         mergeHead = head1;
         mergeHead.next = Merge(head1.next,head2);
     }else{
         mergeHead = head2;
         mergeHead.next = Merge(head1,head2.next);
     }
     return mergeHead;
 }
 1 // 获取单链表中间结点,若链表长度为n(n>0),则返回第n/2 1个结点  
 2 ListNode * GetMiddleNode(ListNode * pHead)  
 3 {  
 4     if(pHead == NULL || pHead->m_pNext == NULL) // 链表为空或只有一个结点,返回头指针  
 5         return pHead;  
 6   
 7     ListNode * pAhead = pHead;  
 8     ListNode * pBehind = pHead;  
 9     while(pAhead->m_pNext != NULL) // 前面指针每次走两步,直到指向最后一个结点,后面指针每次走一步  
10     {  
11         pAhead = pAhead->m_pNext;  
12         pBehind = pBehind->m_pNext;  
13         if(pAhead->m_pNext != NULL)  
14             pAhead = pAhead->m_pNext;  
15     }  
16     return pBehind; // 后面的指针所指结点即为中间结点  
17 }  

注意问题:
1)链表不能断开,且仍为递增顺序;
2)代码鲁棒性,考虑链表为空的情况;

澳门新濠3559 8

//遍历的方式
public static LinkNode Merge(LinkNode head1,LinkNode head2){

         //预判断
         if(head1 == null && head2 == null){
             return null;
         }
         if(head1 == null){
             return head2;
         }
         if(head2 == null){
             return head1;
         }

         LinkNode head;//新的头结点
         LinkNode temp;

         //确定新的头结点
         if(head1.value <= head2.value){
             head = head1;
             temp = head1;
             head1 = head1.next;
         }else{
             head = head2;
             temp = head2;
             head2 = head2.next;
         }
         //合并
         while(head1 != null && head2!=null){
             if(head1.value <= head2.value){
                 temp.next = head1;
                 temp = temp.next;
                 head1 = head1.next;
             }else{
                 temp.next = head2;
                 temp = temp.next;
                 head2 = head2.next;
             }
         }
         //合并剩余的元素
         if(head1 != null){
             temp.next = head1;
         }
         if(head2 != null){
             temp.next = head2;;
         }

         return head;
     }

5. 从尾到头打印单链表

  1. 查找单链表中的倒数第k个结点

对于这种颠倒顺序的问题,我们应该就会想到栈,后进先出。所以,这一题要么自己使用栈,要么让系统使用栈,也就是递归。注意链表为空的情况。时间复杂度为O(n)。参考代码如下:

题目描述:输入一个单链表的头结点,反转该链表并输出反转后的头结点。 (剑指offer,题16)
例如:
链表反转前: 1->3->5->7
链表反转后: 7->5->3->1

自己使用栈:

解题思路 : 从头到尾遍历原链表,使用三个节点pNode、pPrev、pPost 记录当前节点,前一个节点和后一个节点。

澳门新濠3559 9

public static LinkNode ReverseList(LinkNode header){
    if(header == null) return null;

    LinkNode pNode = header;
    LinkNode pPrev = null;   //记录前一个节点
    LinkNode pPost = null;   //记录后一个节点
    while(pNode != null){
        pPost = pNode.next;
        pNode.next = pPrev;
        pPrev = pNode;
        pNode = pPost;
    }
    return pPrev;
}
 1 // 从尾到头打印链表,使用栈  
 2 void RPrintList(ListNode * pHead)  
 3 {  
 4     std::stack<ListNode *> s;  
 5     ListNode * pNode = pHead;  
 6     while(pNode != NULL)  
 7     {  
 8         s.push(pNode);  
 9         pNode = pNode->m_pNext;  
10     }  
11     while(!s.empty())  
12     {  
13         pNode = s.top();  
14         printf("%dt", pNode->m_nKey);  
15         s.pop();  
16     }  
17 }  

注意问题:链表为空和只有1个节点的问题。

澳门新濠3559 10

  1. ****从尾到头打印单链表****

使用递归函数:

题目描述:输入一个链表的头结点,从尾到头反过来打印出每个节点的值. (剑指offer,题5)

澳门新濠3559 11

7.1 解法1:在允许修改链表的结构的情况下,可以先反转链表,然后从头到尾输出。

 1 // 从尾到头打印链表,使用递归  
 2 void RPrintList(ListNode * pHead)  
 3 {  
 4     if(pHead == NULL)  
 5     {  
 6         return;  
 7     }  
 8     else  
 9     {  
10         RPrintList(pHead->m_pNext);  
11         printf("%dt", pHead->m_nKey);  
12     }  
13 }  

7.2 解法2:在不允许修改链表的结构的情况下,可以使用栈实现。
遍历的顺序是从头到尾的顺序,可输出的顺序却是从尾到头。也就是说第一个遍历到的节点最后一个输出,而最后一个遍历到的节点第一个输出。这就是典型的“后入先出”,我们可以用栈来实现这种顺序。

澳门新濠3559 12

 public static void reversePrint(LinkNode header){
     if(header == null) return;

     Stack<LinkNode> stack  = new Stack<>();
     LinkNode temp = header;

     while(temp!=null){
         stack.push(temp);
         temp = temp.next;
     }

     while(!stack.empty()){
         System.out.println(stack.pop().value);
     }
 }

6. 已知两个单链表pHead1 和pHead2 各自有序,把它们合并成一个链表依然有序

7.3 解法3:在不允许修改链表的结构的情况下,可以使用递归实现。(递归的本质上就是一个栈结构)
要想实现反过来输出链表,每访问一个节点的时候,先递归输出它后面的节点,再输出节点自身,这样链表的输出结果就反过来了。

这个类似归并排序。尤其注意两个链表都为空,和其中一个为空时的情况。只需要O(1)的空间。时间复杂度为O(max(len1, len2))。参考代码如下:

 public static void reversePrint(LinkNode header){
     if(header == null) return;

     reversePrint(header.next);
     System.out.println(header.value);
 }

澳门新濠3559 13

代码简洁,但是链表非常长的情况下可能会导致函数调用栈溢出。所以显示使用栈基于循环实现的代码的鲁棒性会更好。

 1 // 合并两个有序链表  
 2 ListNode * MergeSortedList(ListNode * pHead1, ListNode * pHead2)  
 3 {  
 4     if(pHead1 == NULL)  
 5         return pHead2;  
 6     if(pHead2 == NULL)  
 7         return pHead1;  
 8     ListNode * pHeadMerged = NULL;  
 9     if(pHead1->m_nKey < pHead2->m_nKey)  
10     {  
11         pHeadMerged = pHead1;  
12         pHeadMerged->m_pNext = NULL;  
13         pHead1 = pHead1->m_pNext;  
14     }  
15     else  
16     {  
17         pHeadMerged = pHead2;  
18         pHeadMerged->m_pNext = NULL;  
19         pHead2 = pHead2->m_pNext;  
20     }  
21     ListNode * pTemp = pHeadMerged;  
22     while(pHead1 != NULL && pHead2 != NULL)  
23     {  
24         if(pHead1->m_nKey < pHead2->m_nKey)  
25         {  
26             pTemp->m_pNext = pHead1;  
27             pHead1 = pHead1->m_pNext;  
28             pTemp = pTemp->m_pNext;  
29             pTemp->m_pNext = NULL;  
30         }  
31         else  
32         {  
33             pTemp->m_pNext = pHead2;  
34             pHead2 = pHead2->m_pNext;  
35             pTemp = pTemp->m_pNext;  
36             pTemp->m_pNext = NULL;  
37         }  
38     }  
39     if(pHead1 != NULL)  
40         pTemp->m_pNext = pHead1;  
41     else if(pHead2 != NULL)  
42         pTemp->m_pNext = pHead2;  
43     return pHeadMerged;  
44 } 
  1. 删除链表结点

澳门新濠3559 14

题目描述:给定链表的头指针和一个节点指针,在O(1)时间删除该节点。 (剑指offer,题13)

也有如下递归解法:

8.1 普通思路:平均时间复杂度O(n)
从链表的头结点开始,顺序遍历要删除的节点,并在链表中删除该节点。

澳门新濠3559 15

 public void delete(LinkNode head,LinkNode toBeDeleted){

     if(head == null || toBeDeleted == null)
         return;

     LinkNode prev = head;
     LinkNode temp = head.next;

     while( temp != null ){
         if(temp.value == toBeDeleted.value){
             prev.next = temp.next;
             break;
         }else{
             temp = temp.next;
             prev = prev.next;
         }
     }

 }
 1 ListNode * MergeSortedList(ListNode * pHead1, ListNode * pHead2)  
 2 {  
 3     if(pHead1 == NULL)  
 4         return pHead2;  
 5     if(pHead2 == NULL)  
 6         return pHead1;  
 7     ListNode * pHeadMerged = NULL;  
 8     if(pHead1->m_nKey < pHead2->m_nKey)  
 9     {  
10         pHeadMerged = pHead1;  
11         pHeadMerged->m_pNext = MergeSortedList(pHead1->m_pNext, pHead2);  
12     }  
13     else  
14     {  
15         pHeadMerged = pHead2;  
16         pHeadMerged->m_pNext = MergeSortedList(pHead1, pHead2->m_pNext);  
17     }  
18     return pHeadMerged;  
19 }  

8.2 改进思路:平均时间复杂度O(1)
前一种方法之所以要从头开始查找,是因为我们需要得到被删除节点的前一个节点,但是想要删除节点并不一定非要找到前一个节点。由于在单链表中可以很方便的得到删除节点的下一个节点,如果我们把下一个节点的内容复制到需要删除的节点上覆盖原有的内容,再把下一个节点删除,就相当于把需要删除的节点删除了。

澳门新濠3559 16

public class Test {
 /** 
  * 链表结点 
  */  
 public static class ListNode {  
     int value; // 保存链表的值  
     ListNode next; // 下一个结点  
 } 
 /** 
  * 【注意1:这个方法和文本上的不一样,书上的没有返回值,这个因为JAVA引用传递的原因, 
  *   如果删除的结点是头结点,如果不采用返回值的方式,那么头结点永远删除不了】 
  * 【注意2:输入的待删除结点必须是待链表中的结点,否则会引起错误,这个条件由用户进行保证】 
  * 
  * @param head        链表表的头 
  * @param toBeDeleted 待删除的结点 
  * @return 删除后的头结点 
  **/
 public static ListNode deleteNode(ListNode head,ListNode toBeDeleted){
     //预判断
     if(head == null)
         return null;
     if(toBeDeleted == null){
         return head;
     }
     // 如果删除的是头结点,直接返回头结点的下一个结点  
     if(head.value == toBeDeleted.value){
         return head.next;
     }
     // 在多个节点的情况下,如果删除的是最后一个元素  
     if(toBeDeleted.next == null){
         // 找待删除元素的前驱  
         ListNode temp = head;
         while(temp.next.value != toBeDeleted.value){
             temp = temp.next;
         }
         // 删除待结点  
         temp.next = null;
     }else{
         // 在多个节点的情况下,如果删除的是某个中间结点  
         toBeDeleted.value =  toBeDeleted.next.value;
         toBeDeleted.next  = toBeDeleted.next.next;
     }
    // 返回删除节点后的链表头结点  
     return head;
 }

 /** 
  * 输出链表的元素值 
  * 
  * @param head 链表的头结点 
  */  
 public static void printList(ListNode head) {  
     while (head != null) {  
         System.out.print("  value :"   head.value);  
         head = head.next;  
     }  
     System.out.println();  
 } 

 public static void main(String[] args) {  
     ListNode head1 = new ListNode();  
     head1.value = 1;  
     ListNode head2 = new ListNode();  
     head2.value = 2;
     ListNode head3 = new ListNode();  
     head3.value = 3;  
     ListNode head4 = new ListNode();  
     head4.value = 4;  

     head1.next = head2;
     head2.next = head3;
     head3.next = head4;

     printList(head1);  
     ListNode head = head1;  
     // 删除头结点  
     head = deleteNode(head, head1);
     printList(head);  

     // 删除尾结点  
     head = deleteNode(head, head4);
     printList(head);  

     // 删除中间结点  
     head = deleteNode(head, head3);
     printList(head);  

     ListNode node = new ListNode();  
     node.value = 12;  
     // 删除的结点不在链表中  
     head = deleteNode(head, node);
     printList(head);  
 }  
}

7. 判断一个单链表中是否有环

考察思维创新能力,打破常规。当我们需要删除一个节点时,并不一定要删除这个节点本身,可以先把下一个节点的内容复制过来覆盖原来需要被删除节点的内容,然后把下一个节点删除。

这里也是用到两个指针。如果一个链表中有环,也就是说用一个指针去遍历,是永远走不到头的。因此,我们可以用两个指针去遍历,一个指针一次走两步,一个指针一次走一步,如果有环,两个指针肯定会在环中相遇。时间复杂度为O(n)。参考代码如下:


澳门新濠3559 17

参考资料:

 1 bool HasCircle(ListNode * pHead)  
 2 {  
 3     ListNode * pFast = pHead; // 快指针每次前进两步  
 4     ListNode * pSlow = pHead; // 慢指针每次前进一步  
 5     while(pFast != NULL && pFast->m_pNext != NULL)  
 6     {  
 7         pFast = pFast->m_pNext->m_pNext;  
 8         pSlow = pSlow->m_pNext;  
 9         if(pSlow == pFast) // 相遇,存在环  
10             return true;  
11     }  
12     return false;  
13 }  
  • 剑指offer
  • 剑指 Offer 学习心得
  • 链表面试题Java实现

澳门新濠3559 18


8. 判断两个单链表是否相交

[2015-9-10]

如果两个链表相交于某一节点,那么在这个相交节点之后的所有节点都是两个链表所共有的。也就是说,如果两个链表相交,那么最后一个节点肯定是共有的。先遍历第一个链表,记住最后一个节点,然后遍历第二个链表,到最后一个节点时和第一个链表的最后一个节点做比较,如果相同,则相交,否则不相交。时间复杂度为O(len1 len2),因为只需要一个额外指针保存最后一个节点地址,空间复杂度为O(1)。参考代码如下:

澳门新濠3559 19

 1 bool IsIntersected(ListNode * pHead1, ListNode * pHead2)  
 2 {  
 3         if(pHead1 == NULL || pHead2 == NULL)  
 4                 return false;  
 5   
 6     ListNode * pTail1 = pHead1;  
 7     while(pTail1->m_pNext != NULL)  
 8         pTail1 = pTail1->m_pNext;  
 9   
10     ListNode * pTail2 = pHead2;  
11     while(pTail2->m_pNext != NULL)  
12         pTail2 = pTail2->m_pNext;  
13     return pTail1 == pTail2;  
14 } 

澳门新濠3559 20

**9. 求两个单链表相交的第一个节点
对第一个链表遍历,计算长度len1,同时保存最后一个节点的地址。
对第二个链表遍历,计算长度len2,同时检查最后一个节点是否和第一个链表的最后一个节点相同,若不相同,不相交,结束。
两个链表均从头节点开始,假设len1大于len2,那么将第一个链表先遍历len1-len2个节点,此时两个链表当前节点到第一个相交节点的距离就相等了,然后一起向后遍历,知道两个节点的地址相同。
**

时间复杂度,O(len1 len2)。参考代码如下:

澳门新濠3559 21

 1 ListNode* GetFirstCommonNode(ListNode * pHead1, ListNode * pHead2)  
 2 {  
 3     if(pHead1 == NULL || pHead2 == NULL)  
 4         return NULL;  
 5   
 6     int len1 = 1;  
 7     ListNode * pTail1 = pHead1;  
 8     while(pTail1->m_pNext != NULL)  
 9     {  
10         pTail1 = pTail1->m_pNext;  
11         len1  ;  
12     }  
13   
14     int len2 = 1;  
15     ListNode * pTail2 = pHead2;  
16     while(pTail2->m_pNext != NULL)  
17     {  
18         pTail2 = pTail2->m_pNext;  
19         len2  ;  
20     }  
21   
22     if(pTail1 != pTail2) // 不相交直接返回NULL  
23         return NULL;  
24   
25     ListNode * pNode1 = pHead1;  
26     ListNode * pNode2 = pHead2;  
27         // 先对齐两个链表的当前结点,使之到尾节点的距离相等  
28     if(len1 > len2)  
29     {  
30         int k = len1 - len2;  
31         while(k--)  
32             pNode1 = pNode1->m_pNext;  
33     }  
34     else  
35     {  
36         int k = len2 - len1;  
37         while(k--)  
38             pNode2 = pNode2->m_pNext;  
39     }  
40     while(pNode1 != pNode2)  
41     {  
42         pNode1 = pNode1->m_pNext;  
43         pNode2 = pNode2->m_pNext;  
44     }  
45         return pNode1;  
46 } 

澳门新濠3559 22

10. 已知一个单链表中存在环,求进入环中的第一个节点

首先判断是否存在环,若不存在结束。在环中的一个节点处断开(当然函数结束时不能破坏原链表),这样就形成了两个相交的单链表,求进入环中的第一个节点也就转换成了求两个单链表相交的第一个节点。参考代码如下:

澳门新濠3559 23

 1 ListNode* GetFirstNodeInCircle(ListNode * pHead)  
 2 {  
 3     if(pHead == NULL || pHead->m_pNext == NULL)  
 4         return NULL;  
 5   
 6     ListNode * pFast = pHead;  
 7     ListNode * pSlow = pHead;  
 8     while(pFast != NULL && pFast->m_pNext != NULL)  
 9     {  
10         pSlow = pSlow->m_pNext;  
11         pFast = pFast->m_pNext->m_pNext;  
12         if(pSlow == pFast)  
13             break;  
14     }  
15     if(pFast == NULL || pFast->m_pNext == NULL)  
16         return NULL;  
17   
18     // 将环中的此节点作为假设的尾节点,将它变成两个单链表相交问题  
19     ListNode * pAssumedTail = pSlow;   
20     ListNode * pHead1 = pHead;  
21     ListNode * pHead2 = pAssumedTail->m_pNext;  
22   
23     ListNode * pNode1, * pNode2;  
24     int len1 = 1;  
25     ListNode * pNode1 = pHead1;  
26     while(pNode1 != pAssumedTail)  
27     {  
28         pNode1 = pNode1->m_pNext;  
29         len1  ;  
30     }  
31       
32     int len2 = 1;  
33     ListNode * pNode2 = pHead2;  
34     while(pNode2 != pAssumedTail)  
35     {  
36         pNode2 = pNode2->m_pNext;  
37         len2  ;  
38     }  
39   
40     pNode1 = pHead1;  
41     pNode2 = pHead2;  
42     // 先对齐两个链表的当前结点,使之到尾节点的距离相等  
43     if(len1 > len2)  
44     {  
45         int k = len1 - len2;  
46         while(k--)  
47             pNode1 = pNode1->m_pNext;  
48     }  
49     else  
50     {  
51         int k = len2 - len1;  
52         while(k--)  
53             pNode2 = pNode2->m_pNext;  
54     }  
55     while(pNode1 != pNode2)  
56     {  
57         pNode1 = pNode1->m_pNext;  
58         pNode2 = pNode2->m_pNext;  
59     }  
60     return pNode1;  
61 } 

澳门新濠3559 24

11. 给出一单链表头指针pHead和一节点指针pToBeDeleted,O(1)时间复杂度删除节点pToBeDeleted

对于删除节点,我们普通的思路就是让该节点的前一个节点指向该节点的下一个节点,这种情况需要遍历找到该节点的前一个节点,时间复杂度为O(n)。对于链表,链表中的每个节点结构都是一样的,所以我们可以把该节点的下一个节点的数据复制到该节点,然后删除下一个节点即可。要注意最后一个节点的情况,这个时候只能用常见的方法来操作,先找到前一个节点,但总体的平均时间复杂度还是O(1)。参考代码如下:

澳门新濠3559 25

 1 void Delete(ListNode * pHead, ListNode * pToBeDeleted)  
 2 {  
 3     if(pToBeDeleted == NULL)  
 4         return;  
 5     if(pToBeDeleted->m_pNext != NULL)  
 6     {  
 7         pToBeDeleted->m_nKey = pToBeDeleted->m_pNext->m_nKey; // 将下一个节点的数据复制到本节点,然后删除下一个节点  
 8         ListNode * temp = pToBeDeleted->m_pNext;  
 9         pToBeDeleted->m_pNext = pToBeDeleted->m_pNext->m_pNext;  
10         delete temp;  
11     }  
12     else // 要删除的是最后一个节点  
13     {  
14         if(pHead == pToBeDeleted) // 链表中只有一个节点的情况  
15         {  
16             pHead = NULL;  
17             delete pToBeDeleted;  
18         }  
19         else  
20         {  
21             ListNode * pNode = pHead;  
22             while(pNode->m_pNext != pToBeDeleted) // 找到倒数第二个节点  
23                 pNode = pNode->m_pNext;  
24             pNode->m_pNext = NULL;  
25             delete pToBeDeleted;  
26         }     
27     }  
28 }  

澳门新濠3559 26

编辑:编程 本文来源:面试官也常常用链表来考察面试者的基本能力,

关键词: 澳门新濠3559