浅谈数据结构之线性表基础算法和面试真题（二）

比眉伴天荒 2022-10-01 08:48 143阅读 0赞

[上一篇][Link 1]

### 浅谈数据结构之线性表基础算法和面试真题（二） ###

*  线性表反转算法
 *  线性表取中间节点
 *  两个有序线性表合并
 *   *  递归算法
     *  非递归算法
 *  面试真题
 *   *  链表排序

线性表的基础概念和结构请参考上一篇,ListNode 结构请参考上一篇，本篇讨论线性表的几个算法，开阔算法思路。

# 线性表反转算法 #

算法描述：线性表反转，就是由原来的前一个节点指向后一个节点，变成后一个节点指向前一个节点，例如1，2，3，4的顺序，反转成4，3，2，1。

/** * 反转链表 * 时间复杂度O(n),空间复杂度O(1) * @param head * @return */
    	public static 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;
    	}

# 线性表取中间节点 #

算法描述：如果线性表是1，2，3，4，5，则算法输出的是3的节点，如果是1，2，3，4，算法输出的2。假设定义两个变量，一个一次增加2，一个一次增加1，那么当第一个变量走到末尾的时候，第二个变量刚好到中间。

/** * 取中间节点(偶数取得中间节点前面得那个) * 时间复杂度O(2/n),空间复杂度O(1) * @param head */
    	public static ListNode getMid(ListNode head) { 
    		if (head == null) { 
    			return head;
    		}
    		ListNode fast = head;
    		ListNode slow = head;
    		while (fast.next != null && fast.next.next != null) { 
    			slow = slow.next;
    			fast = fast.next.next;
    		}
    		return slow;		
    	}

# 两个有序线性表合并 #

两个有序线性表，如一个是1，3，5另一个是2，4，6，合并之后是1，2，3，4，5，6.

## 递归算法 ##

/** * 采用递归 * @param head1 * @param head2 * @return */
    	public static ListNode mergeTwoList(ListNode head1, ListNode head2) { 
    		if (head1 == null && head2 == null) { 
    			return null;
    		}
    		
    		if (head1 == null) { 
    			return head2;
    		} 
    		
    		if (head2 == null) { 
    			return head1;
    		}
    		
    		ListNode head = null;
    		if (head1.value > head2.value) { //说明第一个值是取得head2，就要把head2往后移，递归
    			head = head2;
    			head.next = mergeTwoList(head1, head2.next);
    		} else {  //说明第一个值是取得head1，就要把head1往后移，递归
    			head = head1;
    			head.next = mergeTwoList(head1.next, head2);
    		}
    		return head;
    	}

## 非递归算法 ##

/** * 非递归 * @param head1 * @param head2 * @return */
    	public static ListNode mergeTwoList2(ListNode head1, ListNode head2) { 
    		if (head1 == null || head2 == null) { 
    			return head1 != null ? head1 : head2;
    		}
    		
    		//存储排序后的链表
    		ListNode head = head1.value < head2.value ? head1 : head2;
    		//记录head1
    		ListNode cur1 = head == head1 ? head1 : head1;
    		//记录head2
    		ListNode cur2 = head == head1 ? head2 : head1;
    		
    		ListNode pre = null;//cur1前一个元素
    		ListNode next = null;//cur2后一个元素
    		while (cur1 != null && cur2 != null) { 
    			if (cur1.value <= cur2.value) { 
    				pre = cur1;
    				cur1 = cur1.next;
    			} else { 
    			    // 把cur2合并到cur1，相当于插入操作
    				next = cur2.next;
    				pre.next = cur2;
    				cur2.next = cur1;
    				pre = cur2;
    				cur2 = next;
    			}
    			
    		}
    		//判断是不是其中一个已经结束
    		pre.next = cur1 == null? cur2:cur1;
    		return head;
    	}

# 面试真题 #

## 链表排序 ##

描述：一个链表，奇数位升序，偶数位降序，对链表进行排序，例如：183654729，排序后123456789，要求，空间复杂度O(n);  
思路：  
1.按照奇数位和偶数位拆分成两个链表  
2.对偶数位反转  
3.将两个有序链表进行合并  
按照如上的思路，是不是把问题分解成了几个简单的链表操作。直接上代码：

/** * 分三步 * 1.按照奇数位和偶数位拆分成两个链表 * 2.对偶数位反转 * 3.将两个有序链表进行合并 */
    	
    	public static ListNode[] getLists(ListNode head) { 
    		ListNode head1 = null;
    		ListNode head2 = null;
    		
    		ListNode cur1 = null;
    		ListNode cur2 = null;
    		
    		int count = 1;
    		while( head != null) { 
    			if (count % 2 == 1) { 
    				if (cur1 != null) { 
    					cur1.next = head;
    					cur1 = cur1.next;
    				} else { 
    					cur1 = head;
    					head1 = cur1;
    				}
    			} else { 
    				if (cur2 != null) { 
    					cur2.next = head;
    					cur2 = cur2.next;
    				} else { 
    					cur2 = head;
    					head2 = cur2;
    				}
    			}
    			head = head.next;
    			count++;
    		}
    		
    		cur1.next = null;
    		cur2.next = null;
    		
    		ListNode[] nodes = new ListNode[] { head1, head2};
    		return nodes;		
    	}
    	
    	/** * 链表2反转 * @param head * @return */
    	public static 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;
    	}
    	
    	
    	/** * 采用递归合并 * @param head1 * @param head2 * @return */
    	public static ListNode mergeTwoList(ListNode head1, ListNode head2) { 
    		if (head1 == null && head2 == null) { 
    			return null;
    		}
    		
    		if (head1 == null) { 
    			return head2;
    		} 
    		
    		if (head2 == null) { 
    			return head1;
    		}
    		
    		ListNode head = null;
    		if (head1.value > head2.value) { 
    			head = head2;
    			head.next = mergeTwoList(head1, head2.next);
    		} else { 
    			head = head1;
    			head.next = mergeTwoList(head1.next, head2);
    		}
    		
    		return head;
    	}

[Link 1]: https://blog.csdn.net/cuixhao110/article/details/91445284