常见链表面试题

╰半夏微凉° 2022-05-22 02:42 209阅读 0赞

**简单LinkedList 的java代码实现：**

public class LinkedListNode {
    	public int value;
    	public LinkedListNode next;
    
    	public LinkedListNode(int value) {
    		this.value = value;
    		this.next = null;
    	}
    }

public class LinkedList {
    
    	public LinkedListNode head;
    	
    	/*add an element to the tail*/
    	public void add(int v) {
    		if (head == null) {
    			this.head = new LinkedListNode(v);
    		} else {
    			LinkedListNode node = head;
    			while (node.next != null) {
    				node = node.next;
    			}
    			node.next = new LinkedListNode(v);
    		}
    	}
    	
    	/*remove the element that appear first*/
    	public void removeFirst(int v) {
    		/* if to be removed is head node */
    		if (head.value == v) {
    			head = head.next;
    			return;
    		}
    
    		/* iterate to the end and remove target node */
    		LinkedListNode node = head;
    		while (node.next != null) {
    			if (node.next.value == v) {
    				node.next = node.next.next;
    				return;
    			}
    			node = node.next;
    		}
    	}
    
    	public void print() {
    		LinkedListNode node = head;
    		while (node != null) {
    			System.out.print(node.value + " ");
    			node = node.next;
    		}
    		System.out.println();
    	}
    }

**1. Write code to remove duplicated element from an unsorted linked list. 从无序链表中删除重复元素**

来源 Cracking the Code Interview (2nd Edition) Ch2 Q1.

**【解答】**：题目已经明确说明是无序列表，对这类面试题，一般最差的复杂度是 O(NlogN)，也就是需要一次排序过程，所以给出的答案最好要优于O(NlogN)。

**方法一**：除去重复元素，首先想到利用hash。将List迭代一遍，每拿出一个元素，放到hashtable里，并判断是否重复，如果重复则从List中删除该元素。这个算法的时间复杂度是O(N)，但需要O(N)的空间建立hashtable去存放元素。

java代码：[http://pastebin.com/UiqMVxdL][http_pastebin.com_UiqMVxdL]  这里的linkedlist使用的是java.util.\*中的LinkedList。实际面试中往往需要自己实现一个linkedlist。

public static void removeDuplicate(List<Integer> l){
    2.                Hashtable table = new Hashtable();
    3.                for(Iterator<Integer> iter = l.iterator();iter.hasNext();){
    4.                        Integer i = iter.next();
    5.                        if(table.containsKey(i)){
    6.                                iter.remove();
    7.                        }else{
    8.                                table.put(i, true);
    9.                        }
    10.                }
    11.        }

**方法二：**利用**runner pointer**. 这个技巧也是解答LinkedList Problem的重要技巧之一。迭代当前链表，每次迭代利用一个runner去访问之后的元素，删除重复元素。算是naive approach，时间复杂度O(N^2)，空间复杂度O(1)。面试中最先可能想到的应该是这种解答，然后可以优化到第一种方法。

**2. Implement am algorithm to find the kth to last element of a singly linked list. 查找单项链表中，距最后一个元素距离为K的元素。**

来源 Cracking the Code Interview (2nd Edition) Ch2 Q2.

【解答】：**方法一：**如果知道链表的长度N，答案就是从第(N-K)个元素。当然这题也就没有意义了。

**方法二：利用chaser-runner。**首先让runner先移动K位，这时候chaser从链表头部开始，和runner同时以相同的速度迭代链表，当runner到达链表尾部，chaser恰好距离最后一个元素K的距离。时间复杂度O(N), 空间复杂度O(1)。

java代码：[http://pastebin.com/MQczDMvT][http_pastebin.com_MQczDMvT] 这里用到的LinkedList是本文开始时定义的data structure.

public static LinkedListNode kth2Last(LinkedList list, int k) {
    2.                LinkedListNode chaser = list.head;
    3.                LinkedListNode runner = list.head;
    4. 
    5.                int i = 0;
    6.                
    7.                while (i < k) {
    8.                        /*the list must have at least k+1 elements*/
    9.                        if (runner == null) {
    10.                                return null;
    11.                        }
    12.                        runner = runner.next;
    13.                        i++;
    14.                }
    15.                
    16.                /*if the list has exactly k elements*/
    17.                if(runner == null){
    18.                        return null;
    19.                }
    20.                
    21.                
    22.                /*begin chasing*/
    23.                while(runner.next!=null){
    24.                        chaser = chaser.next;
    25.                        runner = runner.next;
    26.                }
    27.                return chaser;
    28.        }

**3. Given a circular linked list, implement an algorithm which returns the node at the beginning of the loop. 查找有环链表环的头部。**

来源 Cracking the Code Interview (2nd Edition) Ch2 Q6.

**【解答】**： 这个题算是经典面试题之一，和Binary Tree的BFS遍历一样，都属于看上去满有水平，实际并没有太多难度的题目，如果遇到了不会做人品可是败成啥样了！？

首先第一问一般是判断该链表有没有环，接着问如果有环的话，找出环开始的节点。

**如果判断是否有环？--**Same technique as the last question. We can use  **runner pointer** to detect if there is a loop. 记得以前在学校里跑1500米的时候，我经常被人套圈…类似的，如果一个链表有环，并且进入环以后，将一直在环里走下去，慢的总是会被快的赶上，套圈。所以我们用两个指针，一个slow runner，一个fast runner，每次slow走1个，fast走2个，如果在某个时刻slow == fast指针，则证明有环。

**如何判断环的开始是哪个节点？**\-- 这个问题也很容易想通。**当两个指针第一次相遇的时候，他们距离环的开始节点还有K个元素，而这K个元素是进入环之前那段链表元素的个数。**怎么证明呢？设想两个runner同时从某个环的同一个点出发，快的runner以2倍于慢的runner速度前进，它们第一次重合一定还是在这个出发点的位置，以后每一次相遇也一定是在这个出发点的位置。So，设想现在进入环前的那一段K个节点，是环的一部分，离环真正的开始节点距离为K，那么两个runner同时出发，第一次碰撞必然还是在距离环开始节点K的位置。**所以，第一次碰撞时，随便将任意一个runner回到链表头部，此时两个runner以同一速度前进，当他们再次相遇的节点，就是环的开始节点。**

java代码:[http://pastebin.com/p35Cwgzv][http_pastebin.com_p35Cwgzv]

public static LinkedListNode findBegin(LinkedList list){
    2.                LinkedListNode slow = list.head;
    3.                LinkedListNode fast = list.head;
    4.                
    5.                /*find the first meeting point*/
    6.                while(fast!=null){
    7.                        fast = fast.next.next;
    8.                        slow = slow.next;
    9.                        if(fast == slow){
    10.                                break;
    11.                        }
    12.                }
    13.                
    14.                /*check if there do have a loop*/
    15.                if(fast == null){
    16.                        return null;
    17.                }
    18.                
    19.                slow = list.head;
    20.                
    21.                /*find the beginning of the loop*/
    22.                while(slow!=fast){
    23.                        slow = slow.next;
    24.                        fast = fast.next;
    25.                }
    26.                return fast;
    27.        }

**4. Implement a function to check if a linked list is a palindrome. 判断链表是不是回文链表。**

来源 Cracking the Code Interview (2nd Edition) Ch2 Q7.

【解答】：经典面试题了。回文就是 0-->1-->2-->1-->0 奇数个节点， 或者 0-->1-->2-->2-->1-->0 偶数个节点。

**方法一：**很自然的想法就是把链表反转，然后对比反转以后的链表和原链表的节点值，并且只要比较反转链表和原链表一办的元素就可以。

**方法二：**利用runner pointer。很多的题目都可以利用这个方法来解决。**Runner pointer和递归是解决链表问题最常用的两个方法。**

定义两个指针，slow runner和fast runner，fast以2倍于slow的速度向链表尾部移动。如有奇数个节点：当fast到达链表尾部时，slow恰好到达链表中间。如有偶数个节点：fast第一次为null时，slow恰好完成了一半节点的访问。把slow访问过的节点元素值压入一个stack里。此后slow继续向链表尾部访问，同时stack里的元素开始出栈（奇数个元素的情况下要跳过中间元素），比较两个元素值，一旦出现不等，则不是回文，否则是。该解法的时间复杂度是O(N)，因为需要一次迭代，同时需要O(N)的空间用作stack来存放链表元素。

java代码 [http://pastebin.com/wZ54iSmq][http_pastebin.com_wZ54iSmq]  这里的List是本文开始定义的数据结构。

1.        public static boolean isPalindrome(LinkedList list){
    2.                LinkedListNode slow = list.head;
    3.                LinkedListNode fast = list.head;
    4.                
    5.                Stack<Integer> stack = new Stack<Integer>();
    6.                while(fast!=null&&fast.next!=null){
    7.                        stack.push(slow.value);
    8.                        slow = slow.next;
    9.                        fast = fast.next.next;
    10.                }
    11.                
    12.                /*if the length of list is odd*/
    13.                if(fast!=null){
    14.                        slow = slow.next;
    15.                }
    16.                
    17.                /*compare elements all the way to the end*/
    18.                while(slow!=null){
    19.                        if(slow.value!=stack.pop().intValue()){
    20.                                return false;
    21.                        }
    22.                        slow = slow.next;
    23.                }
    24.                return true;
    25.        }

转载：[http://blog.csdn.net/tanglinghui/article/details/7618142][http_blog.csdn.net_tanglinghui_article_details_7618142]

[http_pastebin.com_UiqMVxdL]: http://pastebin.com/UiqMVxdL
[http_pastebin.com_MQczDMvT]: http://pastebin.com/MQczDMvT
[http_pastebin.com_p35Cwgzv]: http://pastebin.com/p35Cwgzv
[http_pastebin.com_wZ54iSmq]: http://pastebin.com/wZ54iSmq
[http_blog.csdn.net_tanglinghui_article_details_7618142]: http://blog.csdn.net/tanglinghui/article/details/7618142